算法4之链表

概述

单双链表的反转，单链表实现队列

单链表反转

链表节点的定义

public class ListNode<V> {public V val;public ListNode<V> next;ListNode() {}ListNode(V val) { this.val = val; }ListNode(V val, ListNode<V> next) { this.val = val; this.next = next; }
}

单链表反转，leetcode: https://leetcode.cn/problems/reverse-linked-list/description/

 /*** 单链表的反转* <a href="https://leetcode.cn/problems/reverse-linked-list/description/">...</a>* null-1-2-3-4-5* pre = null* head = 1* next = head.next* head.next = pre* pre = head* head = next* 先记住下一个值，然后改变指针方向。然后pre和head各流转到下一个值*/public ListNode reverseList(ListNode head){if(head == null){return head;}ListNode pre = null;ListNode next = null;while(head != null) {next = head.next;head.next = pre;pre = head;head = next;}return head;}

双链表的反转

双链表节点的定义

public class DoubleNode<V> {V val;DoubleNode<V> next;DoubleNode<V> last;DoubleNode() {}DoubleNode(V val) { this.val = val; }DoubleNode(V val, DoubleNode<V> next, DoubleNode<V> last) { this.val = val; this.next = next; this.last = last;}}

双链表反转

/*** 双链表的反转* -* 思路和单链表一样，只不过是多了一个指针。* 先记住下一个值，然后改变指针方向。然后pre和head各流转到下一个值*/public DoubleNode reverseDoubleList(DoubleNode head){if(head == null){return head;}DoubleNode pre = null;DoubleNode next = null;while(head != null) {next = head.next;head.next = pre;head.last = next;pre = head;head = next;}return head;}

单链表实现队列

class MyQueue<V>{// head记录队列的头节点private ListNode<V> head;// tail记录队列的尾节点private ListNode<V> tail;// 队列大小private int size;// 判空public boolean isEmpty(){return this.size == 0;}// 获取队列长度public int size(){return this.size;}/*** 元素压入队列* 更新head,tail,size* 思路：* 压入第一个元素，比如1，那么head=1，tail=1;* 压入第二个元素，比如2，那么1-2，即head=1, tail=2;* 压入第三个元素，比如3，那么1-2-3，即head=1, tail=3;* ...* 压入第i个元素，比如i，那么1-2-3...-i，即head=1，tail=i;* 每次压入元素时，原来的tail元素指向新压入的元素。即tail.next = cur;* tail都会更新，即tail = cur;* @param value 元素*/public void offer(V value){ListNode<V> cur = new ListNode<>(value);if(tail == null){head = cur;tail = cur;}else{tail.next = cur;tail = cur;}size++;}/*** 元素弹出队列* 遵循队列，先进先出的特点，所以每次弹出的都是队列的head* 思路：* 如果队列不为空* 比如，当前队列是：1-2-3-4-5，head=1，tail=5;* 此时弹出，那么head会更新，head = head.next;** 如果队列为空* 那么head = null; 此时注意tail要和head保持一致，否则会出现head=null，但是tail=5的情况*/public V poll(){V res = null;if(head != null){res = head.val;head = head.next;size--;}else{tail = head;}return res;}// 返回队列头部元素public V peek(){if(head != null){return head.val;}return null;}}