stellogic的个人空间
链表
stellogic Two
  2025-10-09 08:19:48   2025-10-09 08:19:48    

160.相交链表

https://leetcode.cn/problems/intersection-of-two-linked-lists/description/?envType=study-plan-v2&envId=top-100-liked
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

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

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

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

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

示例 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
输出：No intersection
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

提示：

listA 中节点数目为 m
listB 中节点数目为 n
1 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

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

一个想法：分别遍历AB，使用一个Set保存遍历过的节点。如果某次遍历得到的节点在Set里，就是第一个相交的节点。如果某个链表遍历到尾部，则没有相交节点。

时间复杂度O(m+n),空间O(m)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import java.util.HashSet;
import java.util.Set;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

 public class ListNode {
      int val;
      ListNode next;
      ListNode(int x) {
          val = x;
          next = null;
      }
  }

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

进阶:
双指针。
p_a,和p_b。

同时移动两个指针：

  • 如果某个指针为空，比如p_a为空，则把p_a指向b的开头
  • 当两个指针都为空或者指向同一个节点，则返回这个相交节点或者null

实际上，就是两个指针都要遍历两个链表。

  • 如果两个链表有交点，相交后的长度记为l，则p_a遍历了skip_a + l + skip_b,p_b遍历了skip_b + l + skip_a,两个指针肯定会某个时间指向同一个
  • 如果没有交点，则都遍历l_a + l_b，最终同时为null

时间复杂度O(m + n),空间O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p_a = headA;
        ListNode p_b = headB;
        while (true){
            if (p_a == p_b){
                return p_a;
            }
            p_a = p_a == null ? headB : p_a.next;// 如果用if来写，注意要使用else，防止在p_a为null时，直接把p_a移动到了p_a.next
            p_b = p_b == null ? headA : p_b.next;
        }
    }
}

206.翻转链表

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

示例 1：

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

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

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

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

  1. 递归
    遍历找到最后一个，headNew = 最后一个

基本情况：节点数量是1，即head.next == nul，直接返回

本层问题：cur = head,next = cur.next,next_next = next.next,next.next = cur

递归处理：next_next以及之后的

最后 next_next.next = cur.

时间复杂度：O(n),空间复杂度O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */

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; }
 }

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next ==null){
            return head;
        }
        ListNode cur = head;
        while (cur.next != null){
            cur = cur.next;
        }
        ListNode headNew = cur;
        reverseListReverse(head);
        return headNew;
    }
    private void reverseListReverse(ListNode head){
        if (head.next == null){
            return;
        }
        if (head.next.next == null) {
            ListNode cur = head;
            ListNode next = cur.next;
            cur.next = null;
            next.next = cur;
            return;
        }
        ListNode cur = head;
        ListNode next = cur.next;
        ListNode next_next = next.next;
        cur.next = null;
        next.next = cur;
        reverseListReverse(next_next);
        next_next.next = next;

    }
}

上面解法是可以的。

但最好的还是

先翻转head之后的链表。

之后让head.next指向head并把head.next赋值为null

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */

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; }
}


class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
        ListNode headNew = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return headNew;
    }
}
  1. 迭代

对遍历，对每个节点执行操作。cur和prev记录当前和上一个。Listnode next = cur.next,(防止覆盖）cur.next = prev,prev = cur,cur = cur.next.直到cur为null，prev为此时头节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */


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; }
}


class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode cur = head;
        ListNode prev = null;
        while (cur != null){
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur =next;
        }
        return prev;
    }
}

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

234.回文链表

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

示例 1：

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

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

提示：

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

进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

一个想法是，先正向遍历，用一个数组记录。之后把它逆转（其实把数组逆转就行，也可以使用双指针不去逆转数组）。再次遍历记录到一个数组。最后比较两个数组

时间复杂度O(n),空间复杂度O(n).

下面用双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import java.util.ArrayList;
import java.util.List;

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

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

class Solution {
    public boolean isPalindrome(ListNode head) {
        List<Integer> temp = new ArrayList<>();
        ListNode cur = head;
        while (cur != null){
            temp.add(cur.val);
            cur = cur.next;
        }
        int left = 0;
        int right = temp.size() - 1;
        while (left < right){
            if (temp.get(left) != temp.get(right)){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

为什么要这样转成数组？

数组可以O(1)任意访问，链表不可以。正向反向都是O(n)。想要访问最后一个元素，倒数第二个，倒数第三个都需要一次遍历到

我们可以使用递归倒叙遍历

1
2
3
4
function print_values_in_reverse(ListNode head)
    if head is NOT null
        print_values_in_reverse(head.next)
        print head.val

实现的话，frontPointer来作为从前向后遍历的指针，curNode作为从后向前遍历的指针。递归调用栈依然是O(n),时间复杂度也是O(n),因为用了递归实际上比上面解法更差

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
class Solution{
    private ListNode frontPointer;
    private boolean recursivelyCheck(ListNode curNode){
        if (curNode == null){
            //基本情况，默认为true
            return true;
        }
        boolean isInnerPartPalindrome = recursivelyCheck(curNode.next);//递归调用，判断之前的是不是回文
        if (isInnerPartPalindrome == false){
            //如果以前已经不是，直接false
            return false;
        }
        //判断本层
        ListNode frontCur = frontPointer;
        frontPointer = frontPointer.next;
        return frontCur.val == curNode.val;
    }
    public boolean isPalindrome(ListNode head){
        frontPointer = head;
        return recursivelyCheck(head);
    }
}
  1. 满足进阶要求的方法

其实只要把后半段链表翻转，之后和前半段链表比较即可。

可以先遍历一遍计算节点个数，但更好的是使用快慢指针，慢指针一次走一步，快指针一次走两步，快指针到末尾（无法再向后走两步），慢指针就到了前半部分链表的末尾。

如果是奇数个，中间的节点认为是前半部分的末尾。

把后半部分节点进行翻转

之后开始比较即可,注意后半部分为空就停止，这样可以避免比较中心节点

最好的话最后把后半部分再翻转回来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
import java.util.List;

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

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

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null ){
            return true;
        }
        ListNode endOfFirstListPointer = endOfFirstList(head);
        ListNode startOfLastListReversedListPointer = reverse(endOfFirstListPointer.next);
        ListNode firstPointer = head;
        ListNode lastPointer = startOfLastListReversedListPointer;
        while (lastPointer != null){
            if (firstPointer.val != lastPointer.val){
                return false;
            }
            firstPointer = firstPointer.next;
            lastPointer = lastPointer.next;
        }
        ListNode startOfLastListRightOrder = reverse(startOfLastListReversedListPointer);
        return true;
    }

    private ListNode reverse(ListNode head) {
        ListNode cur = head;
        ListNode prev = null;
        while (cur != null){
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
    
    private ListNode endOfFirstList(ListNode head){
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null){//检查fast即可，要先检查fast.next是否是null
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

141.环形链表

https://leetcode.cn/problems/linked-list-cycle/description/?envType=study-plan-v2&envId=top-100-liked
给你一个链表的头节点 head ，判断链表中是否有环。

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

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

示例 1：

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

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

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

提示：

链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个 有效索引 。

进阶：你能用 O(1)（即，常量）内存解决此问题吗？

想法：一个简单的想法就是一直遍历链表使用一个Set储存遍历过的，如果有重复就有环。时空复杂度都是O(n).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.util.HashSet;
import java.util.Set;

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
  class ListNode {
      int val;
      ListNode next;
      ListNode(int x) {
          val = x;
          next = null;
      }
  }

public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> temp = new HashSet<>();
        ListNode cur = head;
        while (cur != null){
            if (temp.contains(cur)){
                return true;
            }
            temp.add(cur);
            cur=cur.next;
        }
        return false;
    }
}

O(1) 复杂度方法：快慢指针

slow一次走一步，fast一次走两步，如果有环两者必定某次相遇，如果没有环则两者始终无法相遇。（fast相对于slow相对速度是1，因此必定能相遇）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class ListNode {
  int val;
  ListNode next;
  ListNode(int x) {
      val = x;
      next = null;
  }
}

public class Solution{
    public boolean hasCycle(ListNode head){
        if (head == null || head.next == null ||head.next.next == null){
            return false;
        }
        ListNode slow = head;
        ListNode fast = head;
        do{
            if (fast == null || fast.next == null){
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }while (slow != fast);
        return true;
    }
}

142.环形链表二

https://leetcode.cn/problems/linked-list-cycle-ii/description/?envType=study-plan-v2&envId=top-100-liked
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

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

不允许修改 链表。

示例 1：

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

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

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

提示：

链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引

进阶：你是否可以使用 O(1) 空间解决此题？

一个想法：不考虑O(1)空间的话很简单，，遍历，用Set记录，遇到第一个 重复的，就是进入环的节点，如果一直到null都没有重复就是没有环

如果还考虑快慢指针，相遇节点不一定是环的起点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.util.HashSet;
import java.util.Set;

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class Solution {
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> temp = new HashSet<>();
        ListNode cur = head;
        while (cur != null){
            if (temp.contains(cur)){
                return cur;
            }
            temp.add(cur);
            cur=cur.next;
        }
        return null;
    }
}

O(1) 解法：快慢指针。

仿照上题，利用快慢指针判断有无环。

image

如图，设相遇时fast走了n圈，则有fast总距离是a+n(b+c)+b

fast路程总是slow的两倍。所以a+n(b+c)+b = 2(a+b) (慢指针只能走不到一圈，相对速度是1，相对距离小于一圈，时间小于走过一圈的时间)

所以a = (n-1)b+nc = c+(n-1)(b+c)

也就是说环起点距离head距离是相遇点距离环起点距离加上n-1圈

因此使用一个新的指针从head开始向前，slow正常运动，最后一定再环起点相遇

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class Solution{
    public ListNode detectCycle(ListNode head){
        if (head == null || head.next == null ||head.next.next == null){
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        do{
            if (fast == null || fast.next == null){
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
        }while (slow != fast);
        ListNode frontHead = head;
        while (frontHead != slow){
            frontHead = frontHead.next;
            slow = slow.next;
        }
        return slow;
    }
}

21.合并两个有序链表

https://leetcode.cn/problems/merge-two-sorted-lists/description/?envType=study-plan-v2&envId=top-100-liked
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

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

输入：l1 = [], l2 = []
输出：[]
示例 3：

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

提示：

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

一个简单的想法：先把两个链表存到数组里面,初始化LastInsertPlace为-1，之后开始遍历首元素较小的数组，对于每一个元素，对另一个数组查找有没有在[num[i],num[i+1])的元素（查找到nums[i+1]即可)（从LastInsertPlace+1开始查找)，如果有，把该节点插在num[i]之后(我们创建一个新的链表，以num[0]为head)，并使用LastInsertPlace记录该元素索引，如果没有，更新lastInsertPlace到查找到的位置，i+1，直到这个数组的末尾如果Last Insert Place小于另一个数组的长度，则把之后的数组一次插入。实际实现时列表代替数组

时间复杂度O(n+m),两个列表每个元素只能遍历一遍，执行O(1)插入操作；

空间复杂度O(n+m)

实际上上面的想法类似于归并排序的合并步骤。但总之这不是最优解；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 1. 将两个链表的所有节点值存到 ArrayList 里面
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();

        ListNode current = l1;
        while (current != null) {
            list1.add(current.val);
            current = current.next;
        }

        current = l2;
        while (current != null) {
            list2.add(current.val);
            current = current.next;
        }

        // 2. 合并两个有序的 ArrayList 到一个新的 resultList
        List<Integer> resultList = new ArrayList<>();
        int p1 = 0; // 指向 list1 的指针
        int p2 = 0; // 指向 list2 的指针

        // 当两个列表都还有元素时，比较并添加较小的元素
        while (p1 < list1.size() && p2 < list2.size()) {
            if (list1.get(p1) <= list2.get(p2)) {
                resultList.add(list1.get(p1));
                p1++;
            } else {
                resultList.add(list2.get(p2));
                p2++;
            }
        }

        // 将剩余的元素（如果有的话）全部添加到结果列表中
        while (p1 < list1.size()) {
            resultList.add(list1.get(p1));
            p1++;
        }
        while (p2 < list2.size()) {
            resultList.add(list2.get(p2));
            p2++;
        }

        // 3. 将最终的 resultList 转换成一个新的链表并返回
        ListNode dummyHead = new ListNode(-1); // 创建一个虚拟头节点以简化操作
        ListNode tail = dummyHead;
        for (int val : resultList) {
            tail.next = new ListNode(val);
            tail = tail.next;
        }

        return dummyHead.next;
    }
}

标准的方法：

  1. 递归

注意到：

实际上整个过程相当于，

如果list1[0] < list2[0]，merge(list[1:],list2)
else, ,merge(list1，list2[1:])

上面是递归情况

基本情况： 任意一个是空，直接返回另一个

本层： 把小的节点添加上去，即list1[0].next = merge……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */
 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; }
 }

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null){
            return list2;
        } else if (list2 == null) {
            return list1;
        }
        if (list1.val < list2.val){
            list1.next = mergeTwoLists(list1.next,list2);
            return list1;
        }else {
            list2.next = mergeTwoLists(list1,list2.next);
            return list2;
        }
    }
}

复杂度:
时间：每次去掉一个头节点，直到去掉完后返回，每次调用的非递归调用都是O(1),所以时间复杂度O(m+n)
空间: 递归深度O(m+n)

  1. 迭代

上面的过程也可以用迭代描述

首先定义一个虚拟头节点，prehead。这个头节点的值等都不重要，只是为了简化代码逻辑。如果没有这个，定义新的headNew = null，需要把headnew为null的情况单独处理

指针p_1,p_2初始化为l1,l2,是当前遍历到的l1l2的节点。cur初始化为prehead，代表新的链表当前的节点。

每个循环中，比较p_1,p_2对应值的大小，把小的接到cur后面，并把对应的指针更新为下一个。最后把cur也更新为下一个。直到任意一个list为空。

直接把非空的链表接到cur后面即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 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; }
 }



class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode prehead = new ListNode(-1,null);
        ListNode cur = prehead;
        ListNode p_1 = list1;
        ListNode p_2 = list2;
        while (p_1 != null && p_2 != null){
            if (p_1.val < p_2.val){
                cur.next = p_1;
                p_1 = p_1.next;
            }else {
                cur.next = p_2;
                p_2 = p_2.next;
            }
            cur = cur.next;
        }
        cur.next = p_1 == null ? p_2 : p_1;
        return prehead.next;
    }
}

下面是不适用虚拟头节点，需要额外初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 如果没有虚拟头节点，我们需要一个变量来存储新链表的头
        ListNode newHead = null;
        // 还需要一个指针来追踪新链表的尾部
        ListNode cur = null;

        // 如果其中一个链表为空，直接返回另一个
        if (list1 == null) return list2;
        if (list2 == null) return list1;

        // 循环开始前，需要先确定 newHead 是谁，代码显得很臃肿
        if (list1.val < list2.val) {
            newHead = list1;
            list1 = list1.next;
        } else {
            newHead = list2;
            list2 = list2.next;
        }
        cur = newHead; // cur 指向新链表的尾部

        // 现在开始循环处理剩余的节点
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                cur.next = list1;
                list1 = list1.next;
            } else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }

        // 连接剩余的链表部分
        if (list1 != null) {
            cur.next = list1;
        } else {
            cur.next = list2;
        }

        return newHead;
    }
}

注意：Java不把null默认为false，需要使用判断运算符

2.两数相加

https://leetcode.cn/problems/add-two-numbers/description/?envType=study-plan-v2&envId=top-100-liked
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

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

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

示例 1：

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

输入：l1 = [0], l2 = [0]
输出：[0]
示例 3：

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

提示：

每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零

一个简单的想法：把这两个链表都先转换成数字，加和后再把结果转换成链表。这个时间复杂度O(m+n),空间复杂度O(1)

！！但这样会数据溢出，100位的数字无法用基本类型表示

最好的方法是模拟法，模拟列竖式

依次遍历，加和，进位记为carry。直到都为null。如果某个先到了null直接认为是0即可

如果遍历结束后carry大于0，需要创建新节点储存

时间复杂度O(max(m,n))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */
  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; }
 }

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode p_1 = l1;
        ListNode p_2 = l2;
        ListNode prehead =new  ListNode(-1,null);
        ListNode cur = prehead;
        int carry = 0;
        while (p_1 != null || p_2 != null){
            int p_1_val = p_1 == null ? 0 : p_1.val;
            int p_2_val = p_2 == null ? 0 : p_2.val;
            int totalSum = p_1_val + p_2_val + carry;
            int thisVal = totalSum % 10;
            carry = totalSum/10;
            ListNode thisNode = new ListNode(thisVal,null);
            cur.next = thisNode;
            cur = cur.next;
            p_1 = p_1 == null ? null : p_1.next;
            p_2 = p_2 == null ? null : p_2.next;
        }
        if (carry != 0){
            ListNode newNode = new ListNode(carry,null);
            cur.next = newNode;
            cur = cur.next;
        }
        return prehead.next;
    }
}

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

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

示例 1：

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

输入：head = [1], n = 1
输出：[]
示例 3：

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

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

进阶：你能尝试使用一趟扫描实现吗？

简单的想法就是先遍历一遍，得到链表长度，算出要删除的节点的索引位置，再次遍历进行删除。

如何一遍扫描呢？一般感觉这种链表一次遍历经常用快慢指针。假设fast走到末尾，slow恰好指向倒数第n个，则fast路程等于slow路程+n，两者速度似乎没有特殊关系。

实际上这个情况可以直接初始就让fast和slow有n的距离，从而fast到末尾slow指向应当删除的指针。

实际的实现可以使用虚拟头节点，这样我们可以避免给删除头节点写额外的判断代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */
 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; }
 }

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode preHead = new ListNode(-1,head);
        ListNode fast = preHead;
        ListNode slow = preHead;
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        while (fast.next != null){//这样slow指向的就是被删除之前的节点
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return preHead.next;
    }
}

还可以采用栈，不过空间复杂度O(n).
栈后进先出，可以遍历链表全部入栈，之后出栈n次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 import java.util.ArrayDeque;
import java.util.Deque;

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;
    }
}

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        Deque<ListNode> stack = new ArrayDeque<>();
        ListNode dummy = new ListNode(-1,head);
        ListNode cur = dummy;
        while (cur != null){
            stack.push(cur);
            cur = cur.next;
        }
        for (int i = 0; i < n ; i++) {
            stack.pop();
        }
        stack.peek().next = stack.peek().next.next;
        return dummy.next;
    }
}

注意：

特性 ArrayList LinkedList ArrayDeque
底层实现 动态数组 双向链表 循环动态数组
随机访问 O(1) O(n) 不支持
首尾增删 O(n) / 摊销 O(1) O(1) 摊销 O(1)
中间增删 O(n) O(n) (定位) 不支持
内存开销 较低 较高 最低
主要接口 List List, Deque Deque
最佳使用场景 频繁的随机访问和遍历，少量增删。 需要同时作为 List 和 Deque，或在迭代时频繁增删。 作为纯粹的栈或队列，性能最佳。

核心建议：

  • 如果你的主要需求是快速访问任意位置的元素，或者只是简单地存储和遍历数据，ArrayList 几乎总是最佳选择。
  • 如果你需要一个栈 (Stack) 或队列 (Queue)，ArrayDeque 是首选，因为它比 LinkedList 更快、更省内存。
  • 只有在非常特殊的场景下，比如你需要在迭代一个列表的过程中频繁地在当前位置插入或删除元素，LinkedList 才可能展现出优势。在现代 Java 编程中，LinkedList 的使用场景已经越来越少了。

24.两两交换链表中的节点

https://leetcode.cn/problems/swap-nodes-in-pairs/description/?envType=study-plan-v2&envId=top-100-liked
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

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

输入：head = []
输出：[]
示例 3：

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

提示：

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

简单的想法就是，cur指针和prev，开始时把cur放在第二个节点，prev放在第一个节点，每次两个指针都移动两步，交换,实际上还需要一个prev之前的指针。实际上下面的迭代法更好。时间复杂度O(n)

更好的方法是：

  1. 迭代法：创建一个哑节点。（如果没有哑节点，更新head时头节点需要额外逻辑），之后用cur指向当前指针。cur初始化到dummy，交换node1 = cur.next,node2=cur.next.next。之后把cur更新到node1.直到cur为null或者cur.next或者cur.next.next为null
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */

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;
    }
}

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(-1, head);
        ListNode cur = dummy;
        while (cur != null && cur.next != null && cur.next.next != null) {
            ListNode node1 = cur.next;
            ListNode node2 = cur.next.next;
            cur.next = node2;
            node1.next = node2.next;
            node2.next = node1;
            cur = node1;
        }
        return dummy.next;
    }
}
  1. 递归法

基本情况：head为null或者head.next为null

交换head，head.next.

交换第三个节点及之后的。

返回新的头节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */
 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; }
 }

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
        ListNode node1 = head.next;
        head.next = node1.next;
        node1.next = head;
        head.next = swapPairs(head.next);
        return node1;
    }
}

时间：每个节点调用一次，每个节点操作O(1),时间复杂度O(n)
空间：递归深度O(n)

25.k个一组链表翻转

https://leetcode.cn/problems/reverse-nodes-in-k-group/description/?envType=study-plan-v2&envId=top-100-liked
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

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

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

示例 1：

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

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

提示：
链表中的节点数目为 n
1 <= k <= n <= 5000
0 <= Node.val <= 1000

进阶：你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？

一个想法就是，先构造一个dummy，使用一个cur，指向要反转的子链表头节点的前面的节点。初始化为dummy。每次记录headChildList = cur.next,对长度为k的子链表翻转，cur.next更新为新的头节点，之后把cur更新为 headChildList。直到cur后面不足k个节点，每次循环前都要检查是否k个

构造一个reverseList方法，传入参数cur和k，进行翻转，使用迭代。返回新的头节点。

时间复杂度:总之每个节点操作都是O(1),时间复杂度O(n)

空间复杂度:O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */
 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; }
 }

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(-1,head);
        ListNode cur = dummy;
        while (true){
            ListNode end = cur;
            boolean hasKNode = true;
            for (int i = 0; i < k; i++) {
                end = end.next;
                if (end == null){
                    hasKNode = false;
                    break;
                }
            }
            if (hasKNode == false){
                return dummy.next;
            }
            ListNode nextGroupStart = end.next;
            ListNode headChildList = cur.next;
            cur.next = reverseList(cur,k);
            headChildList.next = nextGroupStart;
            cur = headChildList;
        }
    }
    private ListNode reverseList(ListNode prehead,int k ){
        ListNode head = prehead.next;
        ListNode cur = head;
        ListNode prev = prehead;
        for (int i = 0; i < k; i++) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
}

下面是官方实现，思路类似。但维护了head，tail节点，更好理解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
    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};
    }
}

183.随机链表的复制

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

深拷贝理解成创建一个和原本对象内容完全一样的全新对象即可。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random –> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random –> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：

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

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

提示：

0 <= n <= 1000
-104 <= Node.val <= 104
Node.random 为 null 或指向链表中的节点。

简单的想法就是遍历，依次创建新节点构造新链表。时间复杂度O(n)

但是random的复制会出现问题。可能某个节点的random指针复制时，指向的对应节点还没有复制。如果先复制完之后再次查找进行random复制需要花费O(n^2).

复杂度升级到O(n^2)主要在于查找时很麻烦，因此可以使用哈希表储存节点。

同时要注意：random指针指向的还是其他的节点，而不是一个索引。题目中说的索引表示仅仅是一种文本表示

  1. 哈希表
    具体来说，第一次遍历，每个节点依次创建新的节点对象，同时把oldNode作为key，newNode作为value放进哈希表。注意，虽然我们没有重构equals和hashcode方法，但这里依然可以。因为Object默认的两个方法都是根据内存地址计算的。我们不存在地址不同的相同对象

之后二次遍历，把指针拼接好

时空都是O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.HashMap;
import java.util.Map;

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) {
        Map<Node,Node> nodeMap = new HashMap<>();
        Node cur = head;
        while (cur != null){
            Node newNode = new Node(cur.val);
            nodeMap.put(cur,newNode);
            cur = cur.next;
        }
        cur = head;
        while (cur != null){
            Node newNode = nodeMap.get(cur);
            newNode.next = nodeMap.get(cur.next);
            newNode.random = nodeMap.get(cur.random);
            cur = cur.next;
        }
        return nodeMap.get(head);
    }
}
  1. 原地修改

先修改原链表，把每个创建的新的节点放在原节点后面。直接在原链表完成映射关系。

形如： A-a–B-b-C-c……。

之后遍历把random指针处理

之后分开链表

注意，每个新节点都是原节点.next

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
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) {
        Node cur = head;
        while (cur != null){
            Node next = cur.next;
            Node newNode = new Node(cur.val);
            cur.next = newNode;
            newNode.next = next;
            cur = next;
        }
        cur = head;
        while (cur != null){
            Node newNode = cur.next;
            newNode.random = cur.random == null ? null : cur.random.next;
            cur = cur.next.next;
        }
        Node dummy = new Node(-1);
        dummy.next = head;
        Node oldNode = head;
        Node newNode = dummy;
        while (oldNode != null){
            Node nextOldNode = oldNode.next.next;
            newNode.next = oldNode.next;
            newNode = newNode.next;
            oldNode.next = nextOldNode;
            oldNode = nextOldNode;
        }
        return dummy.next;
    }
}

这个方法，时间复杂度O(N),空间O(1)

力扣的很多题降低空间复杂度的方法，都是把输入或者输出空间作为辅助空间

148. 排序链表

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

提示：

链表中节点的数目在范围 [0, 5 * 104] 内
-105 <= Node.val <= 105

进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序

简单的想法就是先转换成数组，之后使用排序，再转换回链表。时间复杂度O(nlogn)，空间复杂度O(n)

常数级的话不知道，链表不能O(1)随机访问

实际上，时间复杂度O(nlogn)的算法一般有快排，归并，堆排序。快排最差是O(n^2)，同时需要随机访问来交换元素；堆排序也需要随机访问；归并不需要，只需要不断分成更小的链表，先分割再合并
整体步骤：

  1. 基本条件：链表长度为1直接返回
  2. 找中点
  3. 归并排序中点左侧
  4. 归并排序中点右侧
  5. 合并两个子链表
  6. 返回
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */
 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; }
 }

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }//得到中点slow
        ListNode headRight = sortList(slow.next);
        slow.next = null;
        ListNode headLeft = sortList(head);
        return merge(headLeft,headRight);
    }
    
    private ListNode merge(ListNode head1,ListNode head2){
        ListNode prehead = new ListNode(-1);
        ListNode cur = prehead;
        ListNode p_1 = head1;
        ListNode p_2 = head2;
        while (p_1 != null && p_2 != null){
            if (p_1.val < p_2.val){
                cur.next = p_1;
                p_1 = p_1.next;
                cur = cur.next;
            }
            else {
                cur.next = p_2;
                p_2 = p_2.next;
                cur = cur.next;
            }
        }
        if (p_1 != null){
            cur.next = p_1;
        }
        if (p_2 != null){
            cur.next = p_2;
        }
        return prehead.next;
    }
}

时间O(nlogn),空间O(logn)

要实现常数级，需要不适用递归，使用迭代，自底向上的归并排序

  1. 先看成有n个长度为1的有序（长度为1天然有序）子链表
  2. 合并这些子链表，得到n/2个长度为2的子链表
  3. 在合并长度为2的子链表，得到n/4个长度为4的
  4. 直到subLength 大于等于 总长度n

具体实现

  1. 遍历计算总长度length
  2. 创建哑节点：简化操作
  3. 外层循环（控制子链表长度）：
    • 使用for，让子链表sublength从1开始，每次循环后翻倍，直到subLenth大于等于length
  4. 内层循环（遍历合并）
    • 每次外层循环，从头开始遍历整个链表，将相邻的、长度subLength的子链表两两合并
    • 需要用prev来记录已排序部分的尾部，curr来表示待处理的头部
    • 循环中，：
      1. 定位子链表：从curr开始，找到第一个子链表，head1，长度subLength
      2. 分割：找到head1末尾，切断，之后找到第二个子链表head2
      3. 再次分割，找到head2末尾，和链表剩余部分断开，保存剩余部分的头节点
      4. 合并，调用merge
      5. 链接，把prev.next指向合并后的子链表头部
      6. 更新prev
      7. 更新curr到剩余部分头节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
 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; }
 }

class Solution {
    public ListNode sortList(ListNode head) {
        ListNode cur = head;
        int length = 0;
        while (cur != null){
            cur = cur.next;
            length++;
        }
        ListNode dummy = new ListNode(-1,head);
        for (int subLength = 1; subLength < length; subLength *= 2) {
            cur = dummy.next;
            ListNode prev = dummy;
            while (cur != null) {
                ListNode head1 = cur;
                for (int i = 1; i < subLength && cur.next != null; i++) {
                    cur = cur.next;
                }
                ListNode head2 = cur.next;
                cur.next = null;
                cur = head2;
                if (cur != null){
                    for (int i = 1; i < subLength && cur.next != null; i++) {
                        cur = cur.next;
                    }
                }
                ListNode nextSubList = null;
                if (cur != null){
                    nextSubList = cur.next;
                    cur.next = null;
                }
                ListNode merged = merge(head1,head2);
                prev.next = merged;
                while (prev !=null){
                    prev = prev.next;
                }
                cur = nextSubList;
            }    
        }
        return dummy.next;
    }
    
    private ListNode merge(ListNode head1,ListNode head2){
        ListNode prehead = new ListNode(-1);
        ListNode cur = prehead;
        ListNode p_1 = head1;
        ListNode p_2 = head2;
        while (p_1 != null && p_2 != null){
            if (p_1.val < p_2.val){
                cur.next = p_1;
                p_1 = p_1.next;
                cur = cur.next;
            }
            else {
                cur.next = p_2;
                p_2 = p_2.next;
                cur = cur.next;
            }
        }
        if (p_1 != null){
            cur.next = p_1;
        }
        if (p_2 != null){
            cur.next = p_2;
        }
        return prehead.next;
    }
}

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：

输入：lists = []
输出：[]
示例 3：

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

提示：

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4

这个感觉实质上就是上面的排序链表的合并部分。还是写好merge方法之后直接合并即可
时间复杂度是O(kN)，N是总结点数，k是lists长度，空间O(1)
O(n_0 + (n_0+n_1)+……+(n_0+n_1+……n_k-1))，结果是O(Nk)。

image

上面的式子，k-j小于等于k，所以最终是NK。
同时最坏情况是平均分布，推导也是NK

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */
 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; }
 }

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0){
            return null;
        }
        if (lists.length == 1){
            return lists[0];
        }
        ListNode merged = merge(lists[0],lists[1]);
       for (int i = 2; i < lists.length; i++) {
          merged = merge(merged,lists[i]);
       }
       return merged;
       
    }
    private ListNode merge(ListNode head1,ListNode head2){
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        ListNode p_1 = head1;
        ListNode p_2 = head2;
        while (p_1 != null && p_2 != null){
            if (p_1.val < p_2.val){
                cur.next = p_1;
                cur = cur.next;
                p_1 = p_1.next;
            }else {
                cur.next = p_2;
                cur = cur.next;
                p_2 = p_2.next;
            }
        }
        if (p_1 != null){
            cur.next = p_1;
        }
        if (p_2 != null){
            cur.next = p_2;
        }
        return dummy.next;
    }
}

更好的解法：

  1. 分治法

合并整个链表，划分为合并左侧链表，合并右侧链表，最后合并两个大链表。递归深度logk,每层操作数都是O(N),所以时间复杂度O(Nlogk),空间O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
 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;
   }
}

class Solution {
   public ListNode mergeKLists(ListNode[] lists) {
      if (lists.length == 0) {
         return null;
      }
      if (lists.length == 1) {
         return lists[0];
      }
      return mergeHelper(lists,0,lists.length-1);
   }

   private ListNode mergeHelper(ListNode[] lists, int left, int right) {//递归三要素：基本情况，递归调用，本层
       if (left >= right){
           return lists[left];
       }
      int mid = left + (right - left) / 2;
      ListNode headLeft = mergeHelper(lists, left, mid);
      ListNode headRight = mergeHelper(lists, mid + 1, right);
      return mergeTwoLists(headLeft,headRight);
   }

   private ListNode mergeTwoLists(ListNode head1, ListNode head2) {
      ListNode dummy = new ListNode(-1);
      ListNode cur = dummy;
      ListNode p_1 = head1;
      ListNode p_2 = head2;
      while (p_1 != null && p_2 != null) {
         if (p_1.val < p_2.val) {
            cur.next = p_1;
            cur = cur.next;
            p_1 = p_1.next;
         } else {
            cur.next = p_2;
            cur = cur.next;
            p_2 = p_2.next;
         }
      }
      if (p_1 != null) {
         cur.next = p_1;
      }
      if (p_2 != null) {
         cur.next = p_2;
      }
      return dummy.next;
   }
}

  1. 优先队列

使用一个优先队列，所有头节点入堆

最小头节点自动选择，出队

连接到末尾，并且补充该节点的next（如果有的话）

重复

注意入堆出堆都是O(logk)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
 import java.util.PriorityQueue;

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;
   }
}

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        if (lists.length == 1) {
            return lists[0];
        }
        PriorityQueue<ListNode> listNodePriorityQueue = new PriorityQueue<>((a, b) -> (a.val - b.val));
        for (ListNode node : lists) {
            if (node != null){
                listNodePriorityQueue.add(node);//注意原题目头节点可能为空
            }
        }
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while (!listNodePriorityQueue.isEmpty()) {
            ListNode node = listNodePriorityQueue.poll();
            if (node.next != null) {
                listNodePriorityQueue.add(node.next);
            }
            cur.next = node;
            cur = cur.next;
        }
        return dummy.next;
    }
}

空间复杂度O(k),时间复杂度klog(k)(头节点依次入堆) + 2(n-k)logk（其余节点都要一次出堆一次入堆，虽然最后几次可能不是logk但是累加后还是（logk+……log1也是klogk）） + klogk（头节点也要出堆） = nlogk

146、LRU缓存

https://leetcode.cn/problems/lru-cache/description/?envType=study-plan-v2&envId=top-100-liked
请你设计并实现一个满足 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) 的平均时间复杂度运行。

1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 105
最多调用 2 * 105 次 get 和 put

key 和value考虑使用哈希表储存。

get本身的操作很容易使用O(1)

但是怎么逐出最久没使用的？这是先进先出，似乎可以使用队列。但是如果有元素被重复使用很难办。题目标签提示链表双向链表

考虑使用双向链表储存访问顺序

链表头部（左侧）表示最近使用的，另一端表示最久未使用的。增删都是O(1)。重要的是找到要增删的节点。可以考虑直接在哈希表中存储节点而不是value

注意现存的LinkedList不适用。这个数据结构虽然基于双向链表，但是主要用途是作为List和Deque的实现。无法直接访问节点。节点被封装了

需要自己造一个双向链表。具体来说就是定义一个双向节点类就行。使用private static定义，这个类仅仅希望LRUCache访问，并且应当是属于整个类的，不应当能够访问某个具体的实例。内部关键字默认可见度即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
import java.util.HashMap;

class LRUCache {

   private static class DLinkedListNode {
      int key;
      int value;
      DLinkedListNode prev = null;
      DLinkedListNode next = null;

      public DLinkedListNode(int key, int value) {
         this.value = value;
         this.key = key;
      }

      public DLinkedListNode() {

      }

   }
   
   private HashMap<Integer,DLinkedListNode> map;
   private int capacity;
   private int size;
   private DLinkedListNode preHead;
   private DLinkedListNode nextTail;


   public LRUCache(int capacity) {
       this.capacity = capacity;
       this.size = 0;
       this.map = new HashMap<>(capacity);
       this.preHead = new DLinkedListNode(-1,-1);
       this.nextTail = new DLinkedListNode(-1,-1);
       this.preHead.next = this.nextTail;
       this.nextTail.prev = this.preHead;
   }

   public int get(int key) {
       if (map.containsKey(key)) {
           DLinkedListNode node = map.get(key);
           moveToHead(node);
           return node.value;
       }   
       return -1;
   }

   public void put(int key, int value) {
        if (map.containsKey(key)){
            DLinkedListNode nodeToChange = map.get(key);
            nodeToChange.value = value;
            moveToHead(nodeToChange);
        }else {
           DLinkedListNode node = new DLinkedListNode(key,value);
           map.put(key,node);
           addToHead(node);
           size++;
        }
        if (size > capacity){
            DLinkedListNode nodeToRemove = nextTail.prev;
            removeNode(nodeToRemove);
            map.remove(nodeToRemove.key);
            size--;
        }
   }
   
   private void addToHead(DLinkedListNode node){
       node.next = preHead.next;
       preHead.next.prev = node;
       node.prev = preHead;
       preHead.next = node;
   }
   private void removeNode(DLinkedListNode node){
       node.prev.next = node.next;
       node.next.prev = node.prev;
   }
   private void moveToHead(DLinkedListNode node){
       removeNode(node);
       addToHead(node);
   }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */
链表
2025/10/09/链表/
作者
stellogic
发布于
2025-10-09 08:19
许可
 评论
评论插件加载失败
正在加载评论插件
  1. 1. 160.相交链表
  2. 2. 206.翻转链表
  3. 3. 234.回文链表
  4. 4. 141.环形链表
  5. 5. 142.环形链表二
  6. 6. 21.合并两个有序链表
  7. 7. 2.两数相加
  8. 8. 19.删除链表的倒数第N个节点
  9. 9. 24.两两交换链表中的节点
  10. 10. 25.k个一组链表翻转
  11. 11. 183.随机链表的复制
  12. 12. 148. 排序链表
  13. 13. 23.合并k个升序链表
  14. 14. 146、LRU缓存
  1. 1. 160.相交链表
  2. 2. 206.翻转链表
  3. 3. 234.回文链表
  4. 4. 141.环形链表
  5. 5. 142.环形链表二
  6. 6. 21.合并两个有序链表
  7. 7. 2.两数相加
  8. 8. 19.删除链表的倒数第N个节点
  9. 9. 24.两两交换链表中的节点
  10. 10. 25.k个一组链表翻转
  11. 11. 183.随机链表的复制
  12. 12. 148. 排序链表
  13. 13. 23.合并k个升序链表
  14. 14. 146、LRU缓存