算法4之链表

概述

链表的题目没有太难的算法，纯看熟练度，是必须会。面试笔试不会是直接挂的，或者给面试官留下不好的印象。
单双链表的反转，单链表实现队列，K个一组反转链表。

单链表反转

链表节点的定义

@Data
public class ListNode<T> {public T val;public ListNode<T> next;ListNode() {}ListNode(T val) { this.val = val; }ListNode(T val, ListNode<T> next) { this.val = val; this.next = next; }// 链表对数器// 用数组创建单链表public static <T> ListNode<T> build(T[] arr){if(arr == null || arr.length == 0){return null;}// 创建虚拟头节点ListNode<T> dummy = new ListNode<>();ListNode<T> cur = dummy;for (T item : arr) {cur.next = new ListNode<>(item);cur = cur.next;}return dummy.next;}// 重写toString方法@Overridepublic String toString(){StringBuilder sb = new StringBuilder();sb.append(this.val);ListNode<T> next = this.next;while (next != null){sb.append(" -> ").append(next.val);next = next.next;}return sb.toString();}
}

单链表反转，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;}}

K个一组反转链表

力扣hard: https://leetcode.cn/problems/reverse-nodes-in-k-group/description/
step1 ： 返回第k个元素

public static ListNode getKGroupEnd(ListNode start, int k){int count = 1;while(count < k && start != null){start = start.next;count++;}return start;}

step2 : 反转链表

public static void reverse(ListNode start, ListNode end){// 反转的while循环边界 cur != end.nextend = end.next;// 反转链表经典3指针ListNode cur = start;ListNode pre = null;ListNode next = null;// 先记录下一节点，指针反转。pre，cur指针流转到下一节点while (cur != end){next = cur.next;cur.next = pre;pre = cur;cur = next;}// 反转完成后再改变起始节点的next指针start.next = end;}

step3: 完整流程。拼接各组的操作。

 public static ListNode reverseKGroup(ListNode head, int k){// 先找到第一组的k个节点ListNode start = head;ListNode end = getKGroupEnd(start, k);if(end == null){// 不够k个，所以直接返回return head;}// 记录head，并且head不会再改变了head = end;reverse(start, end);ListNode lastEnd = start;// 循环找剩下的while(lastEnd.next != null){start = lastEnd.next;end = getKGroupEnd(start, k);if(end == null){// 不够k个，所以直接返回return head;}reverse(start, end);// 和上一组连接起来lastEnd.next = end;lastEnd = start;}return head;}