leetcode算法-链表

leetcode算法

(LeetCode-21)合并两个有序链表

题目

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

1 2	输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]

示例 2：

1 2	输入：l1 = [], l2 = [] 输出：[]

示例 3：

1 2	输入：l1 = [], l2 = [0] 输出：[0]

提示：

1
2
3

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

分析

方法1

其实这个问题和前面的“(LeetCode-88) 合并两个有序数组”有非常大的相似之处，同样是合并，同样是有序，所以这个题目中我们同样可以使用类似“双指针”来解决这个问题。每次从两个链表头部取出比较小的数字放到结果中。为此我们需要引入一个结果节点 resultNode ，这可以在最后让我们比较容易地返回合并后的链表

这种方法的时间复杂度是多少呢？因为要把两个链表各循环一遍，所以时间复杂度是O(m+n)，空间复杂度则是O(1)。

当然在实际编码要注意：

1、边界情况。如果 l1 或者 l2 一开始就是空链表，那么没有任何操作需要合并，所以我们只需要返回非空链表即可。

2、因为链表自带指针，所以我们没有必要再单独声明两个指针了。

方法2

我们可以如下递归地定义两个链表里的 merge 操作（忽略边界情况，比如空链表等）：

也就是说，两个链表头部值较小的一个节点与剩下元素的 merge 操作结果合并。

代码示例

public class MergeLink {
    public static void main(String[] args) {
        ListNode node14 = new ListNode(4);
        ListNode node12 = new ListNode(2,node14);
        ListNode node1 = new ListNode(1,node12);

        ListNode node24 = new ListNode(4);
        ListNode node23 = new ListNode(3,node24);
        ListNode node21 = new ListNode(1,node23);

        ListNode node = mergeTwoLists( node1,  node21);
        while(node != null){
            System.out.println(node.val);
            node = node.next;
        }
    }

    // 双指针
    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null) return list2;
        if(list2 == null) return list1;
        ListNode result = new ListNode(0);
        ListNode p = result;
        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                p.next = list1;
                list1 = list1.next;
            }else {
                p.next = list2;
                list2 = list2.next;
            }
            p = p.next;
        }

        if(list1 != null){
            p.next = list1;
        }
        if(list2 != null){
            p.next = list2;
        }
        return result.next;
    }

    // 递归
//    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//        if(list1 == null) return list2;
//        if(list2 == null) return list1;
//        if(list1.val < list2.val){
//            list1.next = mergeTwoLists(list1.next, list2);
//            return list1;
//        }
//        list2.next = mergeTwoLists(list1, list2.next);
//        return list2;
//    }
}

(LeetCode-83) 删除排序链表中的重复元素

题目

给定一个已排序的链表的头 head ，删除所有重复的元素，使每个元素只出现一次。返回已排序的链表。

示例 1：

1 2	输入：head = [1,1,2] 输出：[1,2]

示例 2：

1 2	输入：head = [1,1,2,3,3] 输出：[1,2,3]

提示：

1
2
3

链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序 排列

分析

递归套路解决链表问题：

找终止条件：当head指向链表只剩一个元素的时候，自然是不可能重复的，因此return
想想应该返回什么值：应该返回的自然是已经去重的链表的头节点
每一步要做什么：宏观上考虑，此时head.next已经指向一个去重的链表了，而根据第二步，我应该返回一个去重的链表的头节点。因此这一步应该做的是判断当前的head和head.next是否相等，如果相等则说明重了，返回head.next，否则返回head

代码示例

public class DelDIffNode {
    public static void main(String[] args) {
        ListNode node14 = new ListNode(4);
        ListNode node13 = new ListNode(2,node14);
        ListNode node12 = new ListNode(2,node13);
        ListNode node1 = new ListNode(1,node12);


        node1 = deleteDuplicates( node1);
        while(node1 != null){
            System.out.println(node1.val);
            node1 = node1.next;
        }
    }

    // 遍历
//    public static ListNode deleteDuplicates(ListNode head){
//        if (head == null){
//            return head;
//        }
//        ListNode p = head;
//        while (p.next != null){
//            if(p.val == p.next.val ){
//                p.next = p.next.next;
//            }else {
//                p = p.next;
//            }
//        }
//        return head;
//    }

    // 递归
    public static ListNode deleteDuplicates(ListNode head){
        if (head == null || head.next == null){
            return head;
        }
        ListNode temp = deleteDuplicates(head.next);
        if (head.val == temp.val){
            head.next = temp.next;
        }else {
            head.next = temp;
        }

        return head;
    }

(LeetCode-141) 环形链表

题目

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。否则，返回 false 。

示例 1：

1
2
3

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

1
2
3

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

1
2
3

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

代码示例

public class CycleLink {
    public static void main(String[] args) {
        ListNode node15 = new ListNode(5);
        ListNode node14 = new ListNode(4, node15);
        ListNode node13 = new ListNode(3,node14);
        ListNode node12 = new ListNode(2,node13);
        ListNode node1 = new ListNode(1,node12);
        //node14.next = node1;
        System.out.println(hasCycle(node1));
    }

    // 双指针
    public static boolean hasCycle(ListNode head) {
        ListNode low = head; // 慢指针
        ListNode qui = head; // 快指针
        if(head == null || head.next == null){
            return false;
        }
        while (qui.next != null && qui.next.next != null){
            low = low.next;
            qui = qui.next.next;
            if(low == qui ){
                return true;
            }
        }
        return false;
    }
}

(LeetCode-142)环形链表II

题目

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改链表。

示例 1：

1
2
3

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

1
2
3

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

1
2
3

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

分析

方法一：哈希表
思路与算法

一个非常直观的思路是：我们遍历链表中的每个节点，并将它记录下来；一旦遇到了此前遍历过的节点，就可以判定链表中存在环。借助哈希表可以很方便地实现。

方法二：快慢指针
思路与算法

我们使用两个指针，fast 与 slow。它们起始都位于链表的头部。随后，slow 指针每次向后移动一个位置，而 fast 指针向后移动两个位置。如果链表中存在环，则 fast 指针最终将再次与 slow 指针在环中相遇。

如下图所示，设链表中环外部分的长度为 a。slow 指针进入环后，又走了 bb 的距离与 fast 相遇。此时，fast 指针已经走完了环的 n 圈，因此它走过的总距离为 a+n(b+c)+b=a+(n+1)b+nca+n(b+c)+b=a+(n+1)b+nc。

根据题意，任意时刻，fast 指针走过的距离都为slow 指针的 2 倍。因此，我们有
a+(n+1)b+nc=2(a+b)⟹a=c+(n−1)(b+c)

有了 a=c+(n-1)(b+c)的等量关系，我们会发现：从相遇点到入环点的距离加上 n-1圈的环长，恰好等于从链表头部到入环点的距离。

因此，当发现slow 与 fast 相遇时，我们再额外使用一个指针 ptr。起始，它指向链表头部；随后，它和 slow 每次向后移动一个位置。最终，它们会在入环点相遇。

代码示例

public class CycleLink {
    public static void main(String[] args) {
        ListNode node15 = new ListNode(5);
        ListNode node14 = new ListNode(4, node15);
        ListNode node13 = new ListNode(3,node14);
        ListNode node12 = new ListNode(2,node13);
        ListNode node1 = new ListNode(1,node12);
        node12.next = node1;
        System.out.println(detectCycle(node1).val);
    }

    // HashSet
//    public static ListNode hasCycle(ListNode head) {
//        ListNode pos = head;
//        Set<ListNode> visited = new HashSet<ListNode>();
//        while (pos != null) {
//            if (visited.contains(pos)) {
//                return pos;
//            } else {
//                visited.add(pos);
//            }
//            pos = pos.next;
//        }
//        return null;
//    }

    // 双指针
    public static ListNode detectCycle(ListNode head) {
        ListNode low = head; // 慢指针
        ListNode qui = head; // 快指针
        if(head == null || head.next == null){
            return null;
        }
        while (qui.next != null && qui.next.next != null){
            low = low.next;
            qui = qui.next.next;
            if(low == qui ){
                qui = head;
                while (low != qui ){
                    low = low.next;
                    qui = qui.next;
                }
                return qui;
            }
        }
        return null;
    }
}

(LeetCode-160)相交链表

题目

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据保证整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

示例 2：

输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？

public class IntersectionNode {

    public static void main(String[] args) {
        ListNode node7 = new ListNode(7);
        ListNode node6 = new ListNode(6, node7);
        ListNode node14 = new ListNode(5, node6);
        ListNode node12 = new ListNode(4,node14);
        ListNode node1 = new ListNode(3,node12);

        ListNode node24 = new ListNode(2,node6);
        ListNode node23 = new ListNode(1,node24);
        ListNode node21 = new ListNode(0,node23);

        ListNode aa = getIntersectionNode(node1, node21);
        if(aa == null){
            System.out.println("没有");
        }else {
            System.out.println(aa.val);
        }
    }

    // HashSet
//    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//        if(headA == null) return null;
//        if(headB == null) return null;
//        Set<ListNode> set = new HashSet<ListNode>();
//        while(headA != null){
//            set.add(headA);
//            headA = headA.next;
//        }
//
//        while(headB != null){
//            if (set.contains(headB)) {
//                return headB;
//            }
//            headB = headB.next;
//        }
//        return null;
//    }

    // 双指针
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null ) return null;

        ListNode pA = headA, pB = headB;
        while(pA != pB){
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }

        return pA;
    }

(LeetCode-206)反转链表

题目

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例1

1 2	输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]

示例 2：

1 2	输入：head = [1,2] 输出：[2,1]

示例 3：

1 2	输入：head = [] 输出：[]

分析

方法一

双指针

定义两个指针： prepre 和 curcur ；prepre 在前 curcur 在后。
每次让 prepre 的 nextnext 指向 curcur ，实现一次局部反转
局部反转完成之后，prepre 和 curcur 同时往前移动一个位置
循环上述过程，直至 prepre 到达链表尾部

方法二

递归

使用递归函数，一直递归到链表的最后一个结点，该结点就是反转后的头结点，记作 retret .
此后，每次函数在返回的过程中，让当前结点的下一个结点的 nextnext 指针指向当前节点。
同时让当前结点的 nextnext 指针指向 NULLNULL ，从而实现从链表尾部开始的局部反转
递归函数全部出栈后，链表反转完成。

代码示例

public class ReverseList {
    public static void main(String[] args) {

        ListNode node26 = new ListNode(6);
        ListNode node25 = new ListNode(5,node26);
        ListNode node24 = new ListNode(4,node25);
        ListNode node23 = new ListNode(2,node24);
        ListNode node21 = new ListNode(1,node23);

        ListNode node = reverseList(  node21);
        while(node != null){
            System.out.println(node.val);
            node = node.next;
        }
    }

    // 双指针
//    public static ListNode reverseList(ListNode head) {
//        if(head == null){
//            return null;
//        }
//        ListNode preNode = null;      // 临时节点的前一个节点
//        ListNode root = head;      // 临时root节点
//        while (root != null){
//            ListNode temp = root.next;  // 下一个节点
//            root.next = preNode; // 指定新的root的下一个节点
//            preNode  = root;
//            root = temp;
//        }
//        return preNode;
//    }

    // 递归
    public static ListNode reverseList(ListNode head) {
        if(head == null){
            return null;
        }
        if(head.next == null){
            return head;
        }
        ListNode temp = reverseList( head.next);
        head.next.next = head;
        head.next = null;
        return temp;
    }
}

(LeetCode-234) 回文链表

题目

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

1 2	输入：head = [1,2,2,1] 输出：true

示例 2：

1 2	输入：head = [1,2] 输出：false

提示：

链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9

方法2

还可以用双指针结合反转链表的方法来解决这个问题：将链表的后半部分反转（修改链表结构），然后将前半部分和后半部分进行比较。比较完成后我们应该将链表恢复原样。

具体做法是：

快慢指针同时出发。当快指针移动到链表的末尾时，慢指针恰好到链表的中间。通过慢指针将链表分为两部分。然后反转后半部分链表，判断是否回文。至于是否要恢复链表，则看自己喜欢

这种方法的时间复杂度O(n)，空间复杂度O(1)。

代码

public class Palindrome {

    public static void main(String[] args) {
        ListNode node15 = new ListNode(1);
        ListNode node14 = new ListNode(2, node15);
        ListNode node131 = new ListNode(3,node14);
        ListNode node13 = new ListNode(3,node131);
        ListNode node12 = new ListNode(2,node13);
        ListNode node1 = new ListNode(1,node12);
      //  node12.next = node1;
        System.out.println(isPalindrome(node1));
    }

    public static boolean isPalindrome(ListNode head) {
        //
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        // 如果链表是奇数个节点， 把正中间的归到左边
        if(fast != null){
            slow = slow.next;
        }

        // 反转后半部分链表
        slow = reverseList(slow);

        fast = head;
        while(slow != null){
            if(fast.val != slow.val){
                return false;
            }
            fast = fast.next;
            slow = slow.next;
        }
        return true;
    }

    // 反转链表(递归)
    public static ListNode reverseList(ListNode head) {
        if(head == null){
            return null;
        }
        if(head.next == null){
            return head;
        }
        ListNode temp = reverseList( head.next);
        head.next.next = head;
        head.next = null;
        return temp;
    }

(LeetCode-876) 链表的中间结点

题目

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例 2：

1
2
3

输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

提示：

给定链表的结点数介于 1 和 100 之间。

代码

public class MiddleNode {

    public static void main(String[] args) {
        ListNode node15 = new ListNode(6);
        ListNode node14 = new ListNode(5, node15);
        ListNode node131 = new ListNode(4,node14);
        ListNode node13 = new ListNode(3,node131);
        ListNode node12 = new ListNode(2,node13);
        ListNode node1 = new ListNode(1,node12);
        //  node12.next = node1;
        System.out.println(MiddleNode(node1).val);
    }

    public static ListNode MiddleNode(ListNode head) {
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

(LeetCode-2)两数相加

题目

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

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

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

示例 1：

1
2
3

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：

1 2	输入：l1 = [0], l2 = [0] 输出：[0]

示例 3：

1 2	输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 输出：[8,9,9,9,0,0,0,1]

分析

代码

class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
public class AddTwoNumbers {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int carry = 0;
        ListNode p, dumny = new ListNode(0);
        p = dumny;
        while (l1 != null || l2 != null || carry != 0){
            if(l1 != null){
                carry += l1.val;
                l1 = l1.next;
            }
            if(l2 != null){
                carry += l2.val;
                l2 = l2.next;
            }
            p.next = new ListNode(carry % 10);
            carry /= 10;
            p = p.next;
        }
        return dumny.next;
    }
}

(LeetCode-19) 删除链表的倒数第 N 个结点

题目

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

1 2	输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]

示例 2：

1 2	输入：head = [1], n = 1 输出：[]

示例 3：

1 2	输入：head = [1,2], n = 1 输出：[1]

分析

方法一：计算链表长度

思路与算法

一种容易想到的方法是，我们首先从头节点开始对链表进行一次遍历，得到链表的长度 L。随后我们再从头节点开始对链表进行一次遍历，当遍历到第 L−n+1 个节点时，它就是我们需要删除的节点。

为了与题目中的 n 保持一致，节点的编号从 1 开始，头节点为编号 1 的节点。

为了方便删除操作，我们可以从哑节点开始遍历 L−n+1 个节点。当遍历到第 L−n+1 个节点时，它的下一个节点就是我们需要删除的节点，这样我们只需要修改一次指针，就能完成删除操作。

方法二：栈

思路与算法

我们也可以在遍历链表的同时将所有节点依次入栈。根据栈「先进后出」的原则，我们弹出栈的第 n 个节点就是需要删除的节点，并且目前栈顶的节点就是待删除节点的前驱节点。这样一来，删除操作就变得十分方便了。

方法三：双指针

思路与算法

我们也可以在不预处理出链表的长度，以及使用常数空间的前提下解决本题。

由于我们需要找到倒数第 n 个节点，因此我们可以使用两个指针 first 和 second 同时对链表进行遍历，并且 first 比 second 超前 n 个节点。当 first 遍历到链表的末尾时，second 就恰好处于倒数第 n 个节点。

具体地，初始时 first 和 second 均指向头节点。我们首先使用 first 对链表进行遍历，遍历的次数为 n。此时，first 和 second 之间间隔了n−1 个节点，即 first 比 second 超前了 n 个节点。

在这之后，我们同时使用 first 和 second 对链表进行遍历。当 first 遍历到链表的末尾（即 first 为空指针）时，second 恰好指向倒数第 n 个节点。

根据方法一和方法二，如果我们能够得到的是倒数第 n 个节点的前驱节点而不是倒数第 n 个节点的话，删除操作会更加方便。因此我们可以考虑在初始时将 second 指向哑节点，其余的操作步骤不变。这样一来，当 first 遍历到链表的末尾时，second 的下一个节点就是我们需要删除的节点。

代码

public class RemoveNthFromEnd {
    public static void main(String[] args) {
        ListNode node5 = new ListNode(5);
        ListNode node4 = new ListNode(4, node5);
        ListNode node3 = new ListNode(3, node4);
        ListNode node2 = new ListNode(2, node3);
        ListNode node1 = new ListNode(1, node2);
        ListNode temp = removeNthFromEnd(node1, 2);
        System.out.println("");
    }

    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode start = new ListNode(0);
        ListNode slow = start, fast = start;
        fast.next = head;

        // 先移动快指针n步
        for(int i = 1; i <= n + 1; i++){
            fast = fast.next;
        }
        // 同时移动快慢指针
        while (fast != null){
            slow = slow.next;
            fast = fast.next;
        }
        // 去除不要的第N个节点
        slow.next = slow.next.next;
        return start.next;
    }
}

(LeetCode-92) 反转链表 II

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回反转后的链表。

示例 1：

1 2	输入：head = [1,2,3,4,5], left = 2, right = 4 输出：[1,4,3,2,5]

示例 2：

1 2	输入：head = [5], left = 1, right = 1 输出：[5]

分析

方法一：穿针引线

我们以下图中黄色区域的链表反转为例。

使用「206. 反转链表」的解法，反转 left 到 right 部分以后，再拼接起来。我们还需要记录 left 的前一个节点，和 right 的后一个节点。如图所示：

算法步骤：

第 1 步：先将待反转的区域反转；
第 2 步：把 pre 的 next 指针指向反转以后的链表头节点，把反转以后的链表的尾节点的 next 指针指向 succ。

方法二：一次遍历「穿针引线」反转链表（头插法）

方法一的缺点是：如果 left 和 right 的区域很大，恰好是链表的头节点和尾节点时，找到 left 和 right 需要遍历一次，反转它们之间的链表还需要遍历一次，虽然总的时间复杂度为 O(N)，但遍历了链表 2 次，可不可以只遍历一次呢？答案是可以的。我们依然画图进行说明。

我们依然以方法一的示例为例进行说明。

整体思想是：在需要反转的区间里，每遍历到一个节点，让这个新节点来到反转部分的起始位置。下面的图展示了整个流程。

下面我们具体解释如何实现。使用三个指针变量 pre、curr、next 来记录反转的过程中需要的变量，它们的意义如下：

curr：指向待反转区域的第一个节点 left；
next：永远指向 curr 的下一个节点，循环过程中，curr 变化以后 next 会变化；
pre：永远指向待反转区域的第一个节点 left 的前一个节点，在循环过程中不变。

第 1 步，我们使用 ①、②、③ 标注「穿针引线」的步骤。

操作步骤：

先将 curr 的下一个节点记录为 next；
执行操作 ①：把 curr 的下一个节点指向 next 的下一个节点；
执行操作 ②：把 next 的下一个节点指向 pre 的下一个节点；
执行操作 ③：把 pre 的下一个节点指向 next。

第 1 步完成以后「拉直」的效果如下：

第 2 步，同理。同样需要注意 「穿针引线」操作的先后顺序。

第 2 步完成以后「拉直」的效果如下：

第 3 步，同理。

第 3 步完成以后「拉直」的效果如下：

代码

 // 穿针引线
 public ListNode reverseBetween(ListNode head, int left, int right) {
        // 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;

        ListNode pre = dummyNode;
        // 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点
        // 建议写在 for 循环里，语义清晰
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }

        // 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点
        ListNode rightNode = pre;
        for (int i = 0; i < right - left + 1; i++) {
            rightNode = rightNode.next;
        }

        // 第 3 步：切断出一个子链表（截取链表）
        ListNode leftNode = pre.next;
        ListNode curr = rightNode.next;

        // 注意：切断链接
        pre.next = null;
        rightNode.next = null;

        // 第 4 步：同第 206 题，反转链表的子区间
        reverseLinkedList(leftNode);

        // 第 5 步：接回到原来的链表中
        pre.next = rightNode;
        leftNode.next = curr;
        return dummyNode.next;
    }

    private void reverseLinkedList(ListNode head) {
        // 也可以使用递归反转一个链表
        ListNode pre = null;
        ListNode cur = head;

        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
    }


// 一次遍历
 public ListNode reverseBetween(ListNode head, int left, int right) {
        // 设置 dummyNode 是这一类问题的一般做法
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode pre = dummyNode;
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }
        ListNode cur = pre.next;
        ListNode next;
        for (int i = 0; i < right - left; i++) {
            next = cur.next;
            cur.next = next.next;
            next.next = pre.next;
            pre.next = next;
        }
        return dummyNode.next;
    }

(LeetCode-143) 重排链表

题目

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

1	L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

1	L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1：

1 2	输入：head = [1,2,3,4] 输出：[1,4,2,3]

示例 2：

1 2	输入：head = [1,2,3,4,5] 输出：[1,5,2,4,3]

分析

方法二：寻找链表中点 + 链表逆序 + 合并链表

注意到目标链表即为将原链表的左半端和反转后的右半端合并后的结果。

这样我们的任务即可划分为三步：

找到原链表的中点（参考「876. 链表的中间结点」）。
- 我们可以使用快慢指针来 O(N)O(N) 地找到链表的中间节点。
将原链表的右半端反转（参考「206. 反转链表」）。
- 我们可以使用迭代法实现链表的反转。
将原链表的两端合并。
- 因为两链表长度相差不超过 11，因此直接合并即可。

代码

public void reorderList(ListNode head) {
       if (head == null) {
           return;
       }
       ListNode mid = middleNode(head);
       ListNode l1 = head;
       ListNode l2 = mid.next;
       mid.next = null;
       l2 = reverseList(l2);
       mergeList(l1, l2);
   }

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

   public ListNode reverseList(ListNode head) {
       ListNode prev = null;
       ListNode curr = head;
       while (curr != null) {
           ListNode nextTemp = curr.next;
           curr.next = prev;
           prev = curr;
           curr = nextTemp;
       }
       return prev;
   }

   public void mergeList(ListNode l1, ListNode l2) {
       ListNode l1_tmp;
       ListNode l2_tmp;
       while (l1 != null && l2 != null) {
           l1_tmp = l1.next;
           l2_tmp = l2.next;

           l1.next = l2;
           l1 = l1_tmp;

           l2.next = l1;
           l2 = l2_tmp;
       }
   }

(LeetCode-146) LRU 缓存机制

题目

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。
实现 LRUCache 类：

LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

分析

方法一：哈希表 + 双向链表

LRU 缓存机制可以通过哈希表辅以双向链表实现，我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。

双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。
哈希表即为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表中的位置。

这样以来，我们首先使用哈希表进行定位，找出缓存项在双向链表中的位置，随后将其移动到双向链表的头部，即可在 O(1)O(1) 的时间内完成 get 或者 put 操作。具体的方法如下：

对于 get 操作，首先判断 key 是否存在：
- 如果 key 不存在，则返回 -1−1；
- 如果 key 存在，则 key 对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置，并将其移动到双向链表的头部，最后返回该节点的值。
对于 put 操作，首先判断 key 是否存在：
- 如果 key 不存在，使用 key 和 value 创建一个新的节点，在双向链表的头部添加该节点，并将 key 和该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量，如果超出容量，则删除双向链表的尾部节点，并删除哈希表中对应的项；
- 如果 key 存在，则与 get 操作类似，先通过哈希表定位，再将对应的节点的值更新为 value，并将该节点移到双向链表的头部。

上述各项操作中，访问哈希表的时间复杂度为 O(1)O(1)，在双向链表的头部添加节点、在双向链表的尾部删除节点的复杂度也为 O(1)O(1)。而将一个节点移到双向链表的头部，可以分成「删除该节点」和「在双向链表的头部添加节点」两步操作，都可以在 O(1)O(1) 时间内完成。

代码

public class LRUCache {
    public static void main(String[] args) {
        LRUCache2 lru = new LRUCache2(5);
        lru.put(1, 11);
        lru.put(2, 22);
        lru.put(3, 33);
        lru.put(4, 44);
        lru.put(5, 55);
        lru.put(6, 66);
        int num = lru.get(5);
        System.out.println("");
    }
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
        public DLinkedNode() {}
        public DLinkedNode(int _key, int _value) {key = _key; value = _value;}
    }

    private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
    private int size;
    private int capacity;
    private DLinkedNode head, tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        // 使用伪头部和伪尾部节点
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            return -1;
        }
        // 如果 key 存在，先通过哈希表定位，再移到头部
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            // 如果 key 不存在，创建一个新的节点
            DLinkedNode newNode = new DLinkedNode(key, value);
            // 添加进哈希表
            cache.put(key, newNode);
            // 添加至双向链表的头部
            addToHead(newNode);
            ++size;
            if (size > capacity) {
                // 如果超出容量，删除双向链表的尾部节点
                DLinkedNode tail = removeTail();
                // 删除哈希表中对应的项
                cache.remove(tail.key);
                --size;
            }
        }
        else {
            // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
            node.value = value;
            moveToHead(node);
        }
    }

    private void addToHead(DLinkedNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(DLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(DLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }

    private DLinkedNode removeTail() {
        DLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }
}

(LeetCode-23) 合并K个升序链表

题目

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

1 2	输入：lists = [] 输出：[]

示例 3：

1 2	输入：lists = [[]] 输出：[]

分析

方法二：分治合并

思路

将 k 个链表配对并将同一对中的链表合并；
第一轮合并以后， k 个链表被合并成了k/2个链表，平均长度为 k/2n，然后是 4/k 个链表, 8/k 个链表等等；
重复这一过程，直到我们得到了最终的有序链表。

方法三：使用优先队列合并

思路

这个方法和前两种方法的思路有所不同，我们需要维护当前每个链表没有被合并的元素的最前面一个，k 个链表就最多有 k 个满足这样条件的元素，每次在这些元素里面选取 val 属性最小的元素合并到答案中。在选取最小元素的时候，我们可以用优先队列来优化这个过程。

代码

// 分治
public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    public ListNode merge(ListNode[] lists, int l, int r) {
        if (l == r) {
            return lists[l];
        }
        if (l > r) {
            return null;
        }
        int mid = (l + r) >> 1;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    public ListNode mergeTwoLists(ListNode a, ListNode b) {
        if (a == null || b == null) {
            return a != null ? a : b;
        }
        ListNode head = new ListNode(0);
        ListNode tail = head, aPtr = a, bPtr = b;
        while (aPtr != null && bPtr != null) {
            if (aPtr.val < bPtr.val) {
                tail.next = aPtr;
                aPtr = aPtr.next;
            } else {
                tail.next = bPtr;
                bPtr = bPtr.next;
            }
            tail = tail.next;
        }
        tail.next = (aPtr != null ? aPtr : bPtr);
        return head.next;
    }
    
    // 优先队列
    class Status implements Comparable<Status> {
        int val;
        ListNode ptr;

        Status(int val, ListNode ptr) {
            this.val = val;
            this.ptr = ptr;
        }

        public int compareTo(Status status2) {
            return this.val - status2.val;
        }
    }

    PriorityQueue<Status> queue = new PriorityQueue<Status>();

    public ListNode mergeKLists(ListNode[] lists) {
        for (ListNode node: lists) {
            if (node != null) {
                queue.offer(new Status(node.val, node));
            }
        }
        ListNode head = new ListNode(0);
        ListNode tail = head;
        while (!queue.isEmpty()) {
            Status f = queue.poll();
            tail.next = f.ptr;
            tail = tail.next;
            if (f.ptr.next != null) {
                queue.offer(new Status(f.ptr.next.val, f.ptr.next));
            }
        }
        return head.next;
    }

(LeetCode-25) K 个一组翻转链表

题目

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例 1：

1 2	输入：head = [1,2,3,4,5], k = 2 输出：[2,1,4,3,5]

示例 2：

1 2	输入：head = [1,2,3,4,5], k = 3 输出：[3,2,1,4,5]

分析

方法一：模拟

本题的目标非常清晰易懂，不涉及复杂的算法，但是实现过程中需要考虑的细节比较多，容易写出冗长的代码。主要考查面试者设计的能力。

我们需要把链表节点按照 k 个一组分组，所以可以使用一个指针 head 依次指向每组的头节点。这个指针每次向前移动 k 步，直至链表结尾。对于每个分组，我们先判断它的长度是否大于等于 k。若是，我们就翻转这部分链表，否则不需要翻转。

接下来的问题就是如何翻转一个分组内的子链表。翻转一个链表并不难，过程可以参考「206. 反转链表」。但是对于一个子链表，除了翻转其本身之外，还需要将子链表的头部与上一个子链表连接，以及子链表的尾部与下一个子链表连接。如下图所示：

因此，在翻转子链表的时候，我们不仅需要子链表头节点 head，还需要有 head 的上一个节点 pre，以便翻转完后把子链表再接回 pre。

但是对于第一个子链表，它的头节点 head 前面是没有节点 pre 的。太麻烦了！难道只能特判了吗？答案是否定的。没有条件，我们就创造条件；没有节点，我们就创建一个节点。我们新建一个节点，把它接到链表的头部，让它作为 pre 的初始值，这样 head 前面就有了一个节点，我们就可以避开链表头部的边界条件。这么做还有一个好处，下面我们会看到。

反复移动指针 head 与 pre，对 head 所指向的子链表进行翻转，直到结尾，我们就得到了答案。下面我们该返回函数值了。

有的同学可能发现这又是一件麻烦事：链表翻转之后，链表的头节点发生了变化，那么应该返回哪个节点呢？照理来说，前 k 个节点翻转之后，链表的头节点应该是第 k 个节点。那么要在遍历过程中记录第 k 个节点吗？但是如果链表里面没有 k 个节点，答案又还是原来的头节点。我们又多了一大堆循环和判断要写，太崩溃了！

等等！还记得我们创建了节点 pre 吗？这个节点一开始被连接到了头节点的前面，而无论之后链表有没有翻转，它的 next 指针都会指向正确的头节点。那么我们只要返回它的下一个节点就好了。至此，问题解决。

代码

public ListNode reverseKGroup(ListNode head, int k) {
        ListNode hair = new ListNode(0);
        hair.next = head;
        ListNode pre = hair;

        while (head != null) {
            ListNode tail = pre;
            // 查看剩余部分长度是否大于等于 k
            for (int i = 0; i < k; ++i) {
                tail = tail.next;
                if (tail == null) {
                    return hair.next;
                }
            }
            ListNode nex = tail.next;
            ListNode[] reverse = myReverse(head, tail);
            head = reverse[0];
            tail = reverse[1];
            // 把子链表重新接回原链表
            pre.next = head;
            tail.next = nex;
            pre = tail;
            head = tail.next;
        }

        return hair.next;
    }

    public ListNode[] myReverse(ListNode head, ListNode tail) {
        ListNode prev = tail.next;
        ListNode p = head;
        while (prev != tail) {
            ListNode nex = p.next;
            p.next = prev;
            prev = p;
            p = nex;
        }
        return new ListNode[]{tail, head};
    }

(LeetCode-21)合并两个有序链表

题目

分析

方法1

方法2

代码示例

(LeetCode-83) 删除排序链表中的重复元素

题目

分析

代码示例

(LeetCode-141) 环形链表

题目

代码示例

(LeetCode-142)环形链表II

题目

分析

代码示例

(LeetCode-160)相交链表

题目

(LeetCode-206)反转链表

题目

分析

方法一

方法二

代码示例

(LeetCode-234) 回文链表

题目

方法2

代码

(LeetCode-876) 链表的中间结点

题目

代码

(LeetCode-2)两数相加

题目

分析

代码

**(LeetCode-19) **删除链表的倒数第 N 个结点

题目

分析

方法一：计算链表长度

方法二：栈

方法三：双指针

代码

**(LeetCode-92) **反转链表 II

分析

方法一：穿针引线

方法二：一次遍历「穿针引线」反转链表（头插法）

代码

**(LeetCode-143) **重排链表

题目

分析

方法二：寻找链表中点 + 链表逆序 + 合并链表

代码

**(LeetCode-146) **LRU 缓存机制

题目

分析

方法一：哈希表 + 双向链表

代码

(LeetCode-23) 合并K个升序链表

题目

分析

方法二：分治合并

方法三：使用优先队列合并

代码

(LeetCode-25) K 个一组翻转链表

题目

分析

方法一：模拟

代码

(LeetCode-19) 删除链表的倒数第 N 个结点

(LeetCode-92) 反转链表 II

(LeetCode-143) 重排链表

(LeetCode-146) LRU 缓存机制