单链表刷题总结

虚拟头结点

     链表中需要删除结点时常用到虚拟头结点，删除头结点与删除其他结点操作不同，删除其他结点需要该结点的前驱结点指针，而头结点没有前驱结点，为了避免空指针及减少分类操作，设置一个虚拟结点作为头结点的前驱结点，返回链表时返回虚拟结点的next指针。

双指针技巧

     双指针技巧在链表中很常见，通过设置两个指针指向链表结点，可以实现对链表不同位置的操作，从而解决相应问题。

拉拉链

eg：力扣21题：合并两个有序链表

我们来看解法：

ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    // 虚拟头结点
    ListNode dummy = new ListNode(-1), p = dummy;
    ListNode p1 = l1, p2 = l2;

    while (p1 != null && p2 != null) {
        // 比较 p1 和 p2 两个指针
        // 将值较小的的节点接到 p 针
        if (p1.val > p2.val) {
            p.next = p2;
            p2 = p2.next;
        } else {
            p.next = p1;
            p1 = p1.next;
        }
        // p 指针不断前进
        p = p.next;
    }    

    if (p1 != null) {
        p.next = p1;
    }
    
    if (p2 != null) {
        p.next = p2;
    }

    return dummy.next;
}

这道题解法逻辑类似于拉拉链，p1、p2相当于拉链的两侧锯齿，p是拉链的拉索，每次while循环将较小结点接入结果链表。

错位双指针

eg:剑指Offer22题：链表中倒数第k个节点

遍历一次链表解法：

// 返回链表的倒数第 k 个节点
ListNode findFromEnd(ListNode head, int k) {
    ListNode p1 = head;
    // p1 先走 k 步
    for (int i = 0; i < k; i++) &#123;
        p1 = p1.next;
    &#125;
    ListNode p2 = head;
    // p1 和 p2 同时走 n - k 步
    while (p1 != null) &#123;
        p2 = p2.next;
        p1 = p1.next;
    &#125;
    // p2 现在指向第 n - k 个节点即倒数第 k 个结点
    return p2;
&#125;

本题设置两个指针 p1、p2 ,让 p1、p2 指向链表头结点。p1 走 k 步，p2 不动。然后让 p1、p2 同时走，这样当 p1 走到链表末尾空指针时 p2 就走了 n - k 步，还剩k步走完整个链表，p2此时指向链表的倒数第 k 个结点。(ps:其实链表可以看成只有父节点和一个子节点的树，通过后序遍历方式可以倒序遍历链表)

快慢指针

     快慢指针由于两个指针前进的速度不同可导致两指针前进的路程成倍数关系，可用于遍历一次链表找到链表中点、判断链表是否含环等问题。

eg：力扣142题：判断链表是否包含环并返回环的起点
解法：

ListNode detectCycle(ListNode head) {
    ListNode fast, slow;
    //快慢指针初始化指向 head
    fast = slow = head;
    //快指针走到链表末尾时停止
    while (fast != null && fast.next != null) {
        //慢指针走一步，快指针走两步
        fast = fast.next.next;
        slow = slow.next;
        //快慢指针相遇，说明含环
        if (fast == slow) break;
    }
    if (fast == null || fast.next == null) {
        // fast 遇到空指针说明没有环
        return null;
    }

    // 重新指向头结点
    slow = head;

    // 快慢指针同步前进，相交点就是环起点
    while (slow != fast) {
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}

快指针的速度是慢指针的两倍，慢指针走k步则快指针走2k步，快指针比慢指针多走k步，若含环，快慢指针最终会相遇，快指针多走的k步就是在环里面打圈，这k步是整个环步数的整数倍，一定可以将整个环不多也不少地刚刚走完。如果相遇点距环起点为m步，那么从相遇点开始，再走 k-m 步就可以到达环的起点。

链表的递归

     链表是一种兼具迭代和递归性质（可以将原问题分解为相同结构的子问题）的数据结构。对于递归算法，最重要的是明白整个递归函数的定义，根据定义解决具有递归性质的题目。(ps:递归需要堆栈，相比迭代而言，需要更多的空间，使用递归操作链表并不高效。)

eg:反转链表前n个结点

解法：

ListNode successor = null; // 后驱节点

// 反转以 head 为起点的 n 个节点，返回新的头结点
ListNode reverseN(ListNode head, int n) {
    if (n == 1) {
        // 记录第 n + 1 个节点
        successor = head.next;
        return head;
    }
    // 以 head.next 为起点，需要反转前 n - 1 个节点
    ListNode last = reverseN(head.next, n - 1);

    head.next.next = head;
    // 让反转之后的 head 节点和后面的节点连起来
    head.next = successor;

    return last;
}

解法过程：

链表的迭代

     链表有next指针域可以很方便找到下一个结点，对每个结点进行重复操作，它是可迭代的。

eg：力扣92题：反转部分链表
迭代解法：

/** 反转区间 [a, b) 的元素，注意是左闭右开 */
ListNode reverse(ListNode a, ListNode b) {
    ListNode pre, cur, nxt;
    pre = null; cur = a; nxt = a;

    while (cur != b) {
        nxt = cur.next;
        //逐个结点反转
        cur.next = pre;
        //更新指针位置
        pre = cur;
        cur = nxt;
    }
    // 返回反转后的头结点
    return pre;
}

解法过程：