链表

分类：

• 单链表
• 双链表

特点：

• 链表对按索引（下标）查找不友好，时间复杂度O(n)
• 对插入友好，O(1)

遍历：

• 迭代：next 指针的存在使得链表可以使用 while 循环进行迭代
• 递归：链表的结构决定了它可以递归，比如打印当前链表：

public static void print(ListNode head) {
    if (head == null) {
        return;
    }
    
    System.out.println(head.val);
    print(head.next); // 递归
}

技巧：

• 双指针技巧：一快一慢、一先一后
• 哨兵：设置一个伪节点作为 head 的 prev，或者作为 tail 的 next，以便在循环中一致地处理每一个节点

本节目前涵盖了 LeetCode 141，142，160，19，206，203，328，234，21，2，430，138，61 题，部分题目的解法还要参考 LeetCode 上的一些题解进行进一步的理解、优化；

环形链表-双指针技巧

1. 判定链表中是否存在环-141

双指针技巧

问题：如何判定链表中有环？

• 用哈希表，已经存在相同的 key，就表示出现了环
• 双指针技巧：如果出现了环，那么快的指针最终一定会与慢指针相遇；

双指针技巧实现：

• 慢指针每次走1步，快指针每次走2步，可知，假设存在环，那么在慢指针还没开始走第二圈的时候，快指针已经追上了慢指针（极端情况是链表首尾相连，此时，刚好在慢指针走完第一圈时，快指针走完了第二圈，相遇点=环的入口）
• 每次快指针多走一步，当快慢指针相遇时，快指针已经绕环走了 S 圈（S为环的长度）

public class Solution {
    public boolean hasCycle(ListNode head) {
        boolean res = false;

        ListNode slow = head;
        ListNode fast = head;
        while (slow != null && fast != null) {
            slow = slow.next;
            fast = fast.next;
            if (slow == null || fast == null) {
                break;
            }

            fast = fast.next; // fast 多走一步
            if (slow == fast) {
                res = true;
                break;
            }
        }

        return res;
    }
}

2. 找到环的入口-142

思路：

1. 用哈希表存，找到第一个重复的节点
2. 用快慢指针法，根据规则推算，从 head 到环入口的长度=相遇点到入环点的距离 + (n-1) 圈的环长

推导公式，可知：从 head 到入环点的距离，等于 fast和slow 第一次相遇点开始到入环点的距离 + (n-1) * 环长
也就是说：当 fast 和 slow 相遇时，ptr 从 head 出发，slow 从相遇点出发，第一次相遇必然在入环点

    public static ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }

        ListNode slow = head;
        ListNode fast = head;
        while (slow != null) {

            if (fast.next == null || fast.next.next == null) {
                return null;
            }

            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
                ListNode ptr = head;
                while (slow != ptr) {
                    slow = slow.next;
                    ptr = ptr.next;
                }

                return ptr;
            }
        }

        return null;
    }

3. 如何判断两个单向链表是否相交，如果相交，那么找出相交点-160

解法，如果相交，那么我们可以让链表 A 的尾部连接到链表 B 的 head，这样就会形成一个环。此时，判定是否相交就是找这个新链表的入环点。

 /**
     * 获取两个链表相交的点
     * 假设链表中不存在环
     * @param headA
     * @param headB
     * @return
     */
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }

        // 找到第一个链表的尾部
        ListNode cur = headA;
        while (cur.next != null) {
            cur = cur.next;
        }

        // 将第一个链表的 tail 连接到第二个链表的 head，这样就形成了环
        // 根据环形链表中的结论：从 head 出发到入环点的距离 = (n-1) * 环圈 + 相遇点-入环点
        cur.next = headB;
        // 用快慢指针法找到相遇点
        ListNode slow = headA;
        ListNode fast = headA;
        while (slow != null && fast != null) {
            if (slow.next == null || fast.next == null || fast.next.next == null) {
                break;
            }
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
                ListNode ptr = headA;
                // 从相遇点出发
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }

                cur.next = null;
                return ptr;
            }
        }

        cur.next = null;

        return null;
    }

4. 删除倒数第 n 个节点-19

在 O(n) 时间复杂度内删除倒数第 n 个节点

用快慢指针法，快指针先走 n 步，然后快慢指针一起走，当快指针到达链表尾部时，删掉慢指针所在节点；

 /**
     * 两个指针，fast 先走 n 步，然后 slow 出发，当 fast.next == null 时，删掉 slow
     * @param head
     * @param n
     * @return
     */
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return null;
        }

        // 初始化 fast 和 head 两个指针，让 fast 先走 n 步
        ListNode fast = head;
        ListNode slow = head;
        for (int i = 0; i < n - 1; i++) {
            if (fast.next == null) {
                return null;
            }

            fast = fast.next;
        }

        // 上面走了 n - 1 步，再走一步
        if (fast.next == null) {
            // 这一步表示达到末尾了，也就是要删除第一个元素
            return head.next;
        }

        fast = fast.next;

        // fast 和 slow 一起走，直到 fast 达到链表尾部，此时，slow 位置就是要删除的节点
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        if (slow.next != null) {
            slow.next = slow.next.next;
        }
        return head;
    }

经典问题

1. 反转链表-206

• 迭代：一次遍历，从 head 开始，顺序迭代，每次都将 head 的下一个节点放到链表头部，时间复杂度 O(n)，空间复杂度 O(1)
• 递归：每次递归，将第一个节点放到最后；递归需要堆栈，空间复杂度变为 O(n)；（所以对于这一题，还是迭代的方式很简洁）

迭代

public static ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // 每次都将原来的 head 的下一个节点放到第一个节点
        ListNode lastHead = head;
        while (head.next != null) {
            ListNode newHead = head.next;
            head.next = head.next.next;
            newHead.next = lastHead;
            lastHead = newHead;
        }

        return lastHead;
    }

递归

    public static ListNode reverse(ListNode head) {
        if (head.next == null) {
            return head;
        }

        ListNode last = reverse(head.next);
        head.next.next = head; // 把 head 放到 last 的尾部，这样 head 就完成了反转
        head.next = null;
        return last;
    }

扩展：

参考：递归反转链表的一部分

1.1 反转链表前 N 个节点

• 迭代
• 递归

递归实现：

public static ListNode reverseN(ListNode head, int n) {
        if (n == 1) {
            // 结束递归
            successor = head.next;
            return head;
        }

        // 反转后面的元素
        ListNode last = reverseN(head.next, n-1);
        // 将 head 放到第 N + 1 节点前面, 原来的 head.next 已经变成了 last 的tail
        head.next.next = head;
        head.next = successor;
        return last;
}

1.2 反转链表某一部分

/**
     * 反转链表 m - n 中的节点，m >= 1, n <= 链表长度
     * @return
     */
    public static ListNode reverseMN(ListNode head, int m, int n) {
        if (m == 1) {
            // 此时相当于反转链表的前 n 个节点
            return reverseN(head, n);
        }

        // 如果 m > 1，那么我们递归去反转 head.next
        head.next = reverseMN(head.next, m - 1, n - 1);
        return head;
    }    

1.3 k 个一组反转链表-25

LeetCode 25 题，难度：高
https://leetcode-cn.com/problems/reverse-nodes-in-k-group/

思路：

• 反转前 k 个结点，然后递归反转 x * k+1 结点开始的 k 个结点
• 递归结束条件：直到链表剩余结点数小于 k
• 需要准备的方法：反转前 k 个结点

2. 移除链表元素-203

移除 val 等于指定值的节点，分为两种情况：

• 非 head 位置的元素，如果需要删除，只要 prev.next = cur.next 即可
• head 位置的元素，如果需要删除，那么就要将 head = head.next 才行

解决办法：

1. 首先将位于最前面的需要删除的元素删除，确保之后要删除的节点不在 head 位置，然后遍历一遍即可
2. 设置一个哨兵作为伪节点，让 sentinel.next = head，从 sentinel 位置开始遍历即可

第二种的代码：

    public static ListNode removeElements(ListNode head, int val) {
        ListNode sentinel = new ListNode(-1); // 哨兵
        sentinel.next = head;

        ListNode far = sentinel;
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == val) {
                far.next = cur.next;
            } else {
                far = cur;
            }
            cur = cur.next;
        }

        return sentinel.next;
    }

3. 奇偶链表-328

• [ ] 待优化

/**
     * 奇偶转换
     * 奇数位置的节点顺序在前，偶数位置的节点顺序在后
     * @param head
     * @return
     */
    public static ListNode oddEvenList(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode evenHead = null;
        ListNode cur = head;
        while (cur != null) {
            cur = cur.next; // 偶数
            if (evenHead == null) {
                evenHead = cur;
            } else {
                evenHead.next = cur;
            }

            if (cur == null) {
                break;
            }
            cur = cur.next; // 奇数
        }

        return head;
    }

4. 回文链表-234

• 方法 1： List 存储所有节点，两两对比， O(2*n) 时间复杂度，O(n) 空间复杂度
• 方法 2：直接反转整个链表，然后分别读两个链表；时间复杂度 O(n)，空间复杂度 O(n)
• 方法 3：在方法2 基础上进行的优化 —— 用快慢指针找到中间节点，然后反转链表后半部分，然后让指针分别从 head 和 mid 出发来进行比较

方法 2，O(n) 时间复杂度的解法：

• 用快慢指针法找到中间节点，时间 n/2
• 反转链表后半部分, n/2
• 用双指针分别顺序遍历前半部分和后半部分，挨个比较，最坏情况是 O(n/2)
• 再次反转链表后半部分，以恢复链表 n/2

时间复杂度 O(n)，空间复杂度 O(1)

class Solution {
     /**
     * 判定链表是否为回文字符串
     *
     * 1-2 false
     * 1-2-2-1 true
     * @param head
     * @return
     */
    public boolean isPalindrome(ListNode head) {
        
        if (head == null || head.next == null) {
            return true;
        }

        ListNode mid = findMid(head);

        // 反转链表后半部分
        ListNode fast = reverseList(mid.next);

        ListNode slow = head;
        while (slow != mid.next && fast != null) {
            // 注意判定条件，在节点为偶数的情况下，slow 最后等于 mid
            // 在奇数情况下， slow.next 最后等于 mid -> 这种情况，要额外判断一下 fast 是否已经达到末尾了
            if (slow.val != fast.val) {
                reverseList(mid.next);
                return false;
            }
            slow = slow.next;
            fast = fast.next;
        }

        reverseList(mid.next);
        return true;
    }

    /**
     * 找到链表的中间节点
     * 1-2-3-4 => 2
     * 1-2-3 => 2
     * @param head
     * @return
     */
     static ListNode findMid(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            if (fast != null) {
                slow = slow.next;
            }
        }
        return slow;
    }

    public static ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // 1-2-3-4-5 -> 5-4-3-2-1
        // 每次都将原来的 head 的下一个节点放到第一个节点
        ListNode lastHead = head;
        while (head.next != null) {
            ListNode newHead = head.next;
            head.next = head.next.next;
            newHead.next = lastHead;
            lastHead = newHead;
        }

        return lastHead;
    }
}

扩展问题

1. 合并两个有序链表-21

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 思路：都插入到新链表中，这样只需要遍历 O(n)

        ListNode sentinel = new ListNode(-1);
        ListNode cur = sentinel;
        ListNode a = l1;
        ListNode b = l2;
        while (true) {

            if (a == null && b == null) {
                break;
            } else {
                if (a == null) {
                    cur.next = b;
                    b = b.next;
                } else if (b == null) {
                    cur.next = a;
                    a = a.next;
                } else {
                    if (a.val <= b.val) {
                        cur.next = a;
                        a = a.next;
                    } else {
                        cur.next = b;
                        b = b.next;
                    }
                }
                cur = cur.next;
            }
        }

        return sentinel.next;
    }

2. 两数相加-2

题目：给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode sentinel = new ListNode(-1);
        ListNode aCur = l1;
        ListNode bCur = l2;
        ListNode rCur = sentinel;
        int carryNum = 0;
        int thisSum = 0;
        while (true) {
            if (aCur == null && bCur == null) {
                if (carryNum > 0) {
                    rCur.next = new ListNode(carryNum);
                }
                break;
            }

            thisSum = carryNum;
            if (aCur == null) {
                thisSum += bCur.val;
                bCur = bCur.next;
            } else if (bCur == null) {
                thisSum += aCur.val;
                aCur = aCur.next;
            } else {
                thisSum += (aCur.val + bCur.val);
                aCur = aCur.next;
                bCur = bCur.next;
            }

            carryNum = 0;
            if (thisSum >= 10) {
                thisSum = thisSum - 10;
                carryNum = 1;
            }
            rCur.next = new ListNode(thisSum);
            rCur = rCur.next;
        }

        return sentinel.next;
    }

3. 扁平化多级双向链表-430

第一直觉：递归
为什么选择递归呢，因为每一个节点都可能有 child，而每一个 child 也都可能有自己的 child，子子孙孙无穷尽也。显然这里用递归是非常合适的。

/*
// Definition for a Node.
class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
};
*/

class Solution {
    public Node flatten(Node head) {
        if (head == null) {
            return head;
        }

        Node next = null;
        if (head.child == null) {
            if (head.next != null) {
                next = flatten(head.next);
            }
        } else {
            Node oldNext = head.next;
            next = flatten(head.child);

            if (oldNext != null) {
                Node newTail = next;
                while (newTail.next != null) {
                    newTail = newTail.next;
                }

                newTail.next = oldNext;
                oldNext.prev = newTail;
            }
        }

        head.child = null;
        head.next = next;
        if (next != null) {
            next.prev = head;
        }

        return head;
    }
}

4. 复制带随机指针的链表-138

题目描述：链表中每个节点都有一个 random 指针，指向任意的其他节点或空节点。要求实现一个函数，实现链表的深拷贝。

思路：

• 用一个 map 存储原来节点和对应的拷贝节点，第一次遍历链表拷贝 val，第二次遍历链表拷贝 next 和 random

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    public Node copyRandomList(Node head) {
        HashMap<Node, Node> copyMap = new HashMap<>();

        // copy val
        Node cur = head;
        while (cur != null) {
            Node copy = new Node(cur.val);
            copyMap.put(cur, copy);
            cur = cur.next;
        }

        // copy next and random
        cur = head;
        while (cur != null) {
            Node copy = copyMap.get(cur);
            copy.next = copyMap.get(cur.next);
            copy.random = copyMap.get(cur.random);

            cur = cur.next;
        }

        return copyMap.getOrDefault(head, null);
    }
}

5. 旋转链表-61

解法：形成环，然后找到新的 head 并断开环

public ListNode rotateRight(ListNode head, int k) {
        if (k <= 0 || head == null) {
            return head;
        }
        int size = 0;
        ListNode tail = null;
        ListNode cur = head;
        while (cur != null) {
            size++;
            if (cur.next == null) {
                tail = cur;
            }
            cur = cur.next;
        }

        // 变成环
        tail.next = head;

        // 在合适的位置断开环
        int i = 0;
        k = k % size; // 取余数
        while (i < size - k) {
            tail = tail.next;
            i++;
        }

        ListNode newHead = tail.next;
        tail.next = null;
        return newHead;
    }