链表

数据结构

单向链表

public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

基础

反转链表

206. 反转链表

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null) { // 虽然不处理也可以，还是建议做下特判
            return null;
        }
        // pre相当于为head定制的头节点，这样就可以从head开始处理。
        // 如果pre=head, curr=head.next处理，
        // 则需要特殊处理：head.next=null
        ListNode pre = null, curr = head;
        while (curr != null) {
            ListNode tmp = curr.next;
            curr.next = pre;
            pre = curr;
            curr = tmp;
        }
        return pre;
    }
}

快慢指针

• 算好快慢两指针的差距
• 选择迭代方式：快慢/先后

876. 链表的中间结点

class Solution {
    public ListNode middleNode(ListNode head) {
        if (head == null) { // 做特判
            return head;
        }
        
        ListNode fst = head, snd = head.next;
        while (snd != null) {
            fst = fst.next;
            snd = snd.next;
            if (snd != null) {
                snd = snd.next;
            }
        }
        return fst;
    }
}

19. 删除链表的倒数第 N 个结点

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode fast = head;
        // 快指针先走n步
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        // 双指针一起走到底
        ListNode slow = head, pre = null;
        while (fast != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next;
        }
        // 单独处理删除第一个结点的情况
        if (pre == null) {
            return head.next;
        }
        pre.next = slow.next;
        return head;
    }
}

综合

25. K 个一组翻转链表

结合了快慢指针，反转链表。 其实还有优化空间，即goGroupEnd()可以整合在迭代里，减少一遍循环，变量再多几个。

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // mock一个头节点，用于模拟前一组链表，避免边界条件处理
        ListNode mockHead = new ListNode(0, head);
        ListNode preGroupTail = mockHead;
        ListNode currGroupHead = head;
        while (true) {
            ListNode currGroupTail = goGroupEnd(currGroupHead, k);
            if (currGroupTail == null) {
            // 不足k个一组
                preGroupTail.next = currGroupHead;
                break;
            }

            ListNode nextGroupHead = currGroupTail.next;
            // 反转后，首尾互换
            ListNode reverseHead = reverse(currGroupHead, k);
            currGroupTail = currGroupHead;
            // 和上一组连接起来
            preGroupTail.next = reverseHead;
            // 初始化下一组的变量
            currGroupHead = nextGroupHead;
            preGroupTail = currGroupTail;
        }
        return mockHead.next;
    }

    /**
    * 反转连续k个节点，也就是反转一组
    * @return 返回反转后的头节点
    */
    private ListNode reverse(ListNode head, int n) {
        ListNode pre = null, curr = head;
        for (int i = 0; i < n && curr != null; i++) {
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }

    /**
    * 往前走k-1步，走到当前组的最后一个节点
    * @return 如果走到null，说明这组不足k个
    */
    private ListNode goGroupEnd(ListNode head, int n) {
        for (int i = 0; i < n - 1 && head != null; i++) {
            head = head.next;
        }
        return head;
    }
}