链表

单链表

单链表中的每个结点不仅包含值，还包含链接到下一个结点的引用字段。通过这种方式，单链表将所有结点按顺序组织起来。

下面是一个单链表的例子：

image-20250302014159829

蓝色箭头显示单个链接列表中的结点是如何组合在一起的。

结点结构

以下是单链表中结点的典型定义：

1
2
3
4
5
6
7
8
// Definition for singly-linked list.
public class SinglyListNode {
    int val;
    SinglyListNode next;
    SinglyListNode(int x) { 
        val = x; 
    }
}

操作
与数组不同，我们无法在常量时间内访问单链表中的随机元素。 如果我们想要获得第 i 个元素，我们必须从头结点逐个遍历。 我们按索引来访问元素平均要花费 O(N) 时间，其中 N 是链表的长度。

例如，在上面的示例中，头结点是 23。访问第 3 个结点的唯一方法是使用头结点中的“next”字段到达第 2 个结点（结点 6）; 然后使用结点 6 的“next”字段，我们能够访问第 3 个结点。

你可能想知道为什么链表很有用，尽管它在通过索引访问数据时（与数组相比）具有如此糟糕的性能。 在接下来的两篇文章中，我们将介绍插入和删除操作，你将了解到链表的好处。

之后，我们将为你提供练习设计自己的单链表。

添加操作-单链表

如果我们想在给定的结点 prev 之后添加新值，我们应该：

使用给定值初始化新结点 cur；

image-20250302014526988

将 cur 的 next 字段链接到 prev 的下一个结点 next ；

image-20250302014550467

将 prev 中的 next 字段链接到 cur 。

image-20250302014605796

与数组不同，我们不需要将所有元素移动到插入元素之后。因此，您可以在 O(1) 时间复杂度中将新结点插入到链表中，这非常高效。

示例

image-20250302014633315

让我们在第二个结点 6 之后插入一个新的值 9 。

我们将首先初始化一个值为 9 的新结点。然后将结点 9 链接到结点 15 。最后，将结点 6 链接到结点 9 。

插入之后，我们的链表将如下所示：

image-20250302014656020

在开头添加结点

众所周知，我们使用头结点来代表整个列表。

因此，在列表开头添加新节点时更新头结点 head 至关重要。

初始化一个新结点 cur ；
将新结点链接到我们的原始头结点 head。

将 cur 指定为 head 。
例如，让我们在列表的开头添加一个新结点 9 。

我们初始化一个新结点 9 并将其链接到当前头结点 23 。

image-20250302014802365

指定结点 9 为新的头结点。

image-20250302014827867

如何在列表的末尾添加新的结点？我们还能使用类似的策略吗？

  • 在末尾添加节点时，需要遍历到链表末尾，然后将新节点链接到最后一个节点的 next 指针。

删除操作-单链表

如果我们想从单链表中删除现有结点 cur，可以分两步完成：

1、找到 cur 的上一个结点 prev 及其下一个结点 next ；

image-20250302020414598

2、接下来链接 prev 到 cur 的下一个节点 next 。

image-20250302020455299

在我们的第一步中，我们需要找出 prev 和 next。使用 cur 的参考字段很容易找出 next，但是，我们必须从头结点遍历链表，以找出 prev，它的平均时间是 O(N)，其中 N 是链表的长度。因此，删除结点的时间复杂度将是 O(N)。

空间复杂度为 O(1)，因为我们只需要常量空间来存储指针。

示例

image-20250302020632294

让我们尝试把结点 6从上面的单链表中删除。

  1. 从头遍历链表，直到我们找到前一个结点 prev，即结点 23

  2. 将 prev（结点 23）与 next（结点 15）链接

image-20250302020658381

结点 6 现在不在我们的单链表中。

删除第一个结点

如果我们想删除第一个结点，策略会有所不同。

正如之前所提到的，我们使用头结点 head 来表示链表。我们的头是下面示例中的黑色结点 23。

image-20250302020725913

如果想要删除第一个结点，我们可以简单地将下一个结点分配给 head。也就是说，删除之后我们的头将会是结点 6。

image-20250302020742955

链表从头结点开始，因此结点 23 不再在我们的链表中。

删除最后一个结点呢？我们还能使用类似的策略吗？

在自定义的单链表中，删除最后一个节点需要遍历链表，找到倒数第二个节点，然后将其 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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class Node {
    int val;       // 节点数据
    Node next;      // 指向下一个节点的指针

    // 构造函数
    public Node(int val) {
        this.val = val;
        this.next = null;
    }
}

class SinglyLinkedList {
    private Node head; // 链表头节点
    private int size;  // 链表长度

    // 构造函数
    public SinglyLinkedList() {
        this.head = null;
        this.size = 0;
    }

    // 在链表末尾添加新节点
    public void add(int val) {
        Node newNode = new Node(val);
        if (head == null) {
            head = newNode;
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
        size++;
    }

    // 删除链表中的最后一个节点
    public void removeLast() {
        if (head == null) {
            // 链表为空，直接返回
            return;
        }
        if (head.next == null) {
            // 链表只有一个节点，删除头节点
            head = null;
        } else {
            // 链表有多个节点，找到倒数第二个节点
            Node current = head;
            while (current.next.next != null) {
                current = current.next;
            }
            // 将倒数第二个节点的 next 指针设置为 null
            current.next = null;
        }
        size--;
    }

    // 打印链表中的所有节点数据
    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.val + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
}

例题：设计链表

你可以选择使用单链表或者双链表，设计并实现自己的链表。

单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。

如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

实现 MyLinkedList 类：

MyLinkedList() 初始化 MyLinkedList 对象。
int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。

示例：

输入
[“MyLinkedList”, “addAtHead”, “addAtTail”, “addAtIndex”, “get”, “deleteAtIndex”, “get”]
[[], [1], [3], [1, 2], [1], [1], [1]]
输出
[null, null, null, null, 2, null, 3]

解释
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2); // 链表变为 1->2->3
myLinkedList.get(1); // 返回 2
myLinkedList.deleteAtIndex(1); // 现在，链表变为 1->3
myLinkedList.get(1); // 返回 3

提示：

0 <= index, val <= 1000
请不要使用内置的 LinkedList 库。
调用 get、addAtHead、addAtTail、addAtIndex 和 deleteAtIndex 的次数不超过 2000 。

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
//节点类
class Node{
    int val;//节点的值
    Node next;//下一个节点

    //构造器
    public Node(int val){
        this.val = val;
        this.next = null;
    }
}
class MyLinkedList {

    private int size; //链表的大小
    private Node head;//单链表的头结点

    public MyLinkedList() {
        this.size = 0;
        this.head = null;
    }

    public int get(int index) {
        Node current = head;//当前节点
        //排除下标无效的情况
        if(index < 0 || index >= size){
            return -1;
        }
        //一直到下标处的位置
        for(int i = 0 ; i < index ; i++){
            current = current.next;
        }
        //返回下标的值
        return current.val;
    }

    public void addAtHead(int val) {
        Node newNode = new Node(val);//初始化新节点
        Node current = head;//当前节点是头结点
        newNode.next = current;//新节点指向头结点
        head = newNode;//头结点变成新节点
        size++;//链表的大小+1
    }

    public void addAtTail(int val) {
        Node current = head;//当前节点是头结点
        Node newNode = new Node(val);
        if(current == null){
            head = newNode;
            size++;
            return;
        }
        //遍历到链表最后
        for(int i = 0 ; i < size - 1; i++ ){
            current = current.next;
        }
        current.next = newNode;//最后的节点指向新节点
        size++;//链表大小+1
    }

    public void addAtIndex(int index, int val) {
        //排除不合理下标
        if(index < 0 || index > size){
            return ;
        }
        //如果是在开头加节点，这里不用size++，因为方法里面已经+过了
        if(index == 0){
            addAtHead(val);
            return;
        }
        //如果在结尾加节点
        if(index == size){
            addAtTail(val);
            return;
        }
        //在链表中间加节点
        Node newNode = new Node(val);//创建新节点
        Node current = head;//当前节点是头结点
        for(int i = 0 ; i < index - 1 ; i++){//遍历到当前节点的上一个节点
            current = current.next;
        }
        //新节点指向当前节点的下一个节点
        newNode.next = current.next;
        //当前节点指向新节点
        current.next = newNode;
        //链表大小+1
        size++;
    }

    public void deleteAtIndex(int index) {
        //排除不合理下标
        if(index < 0 || index >= size){
            return ;
        }
        //如果是删除头节点
        if(index == 0){
            Node current = head;//当前节点是头结点
            head = current.next;//把当前节点的下一个节点设置为头结点
            current.next = null;//删除当前节点
            size--;//链表大小-1
            return;
        }
        //如果删除尾部节点
        if(index == size - 1){
            Node current = head;//当前节点是头结点
            for(int i = 0 ; i < index - 1 ; i++){//遍历到当前节点的上一个节点
                current = current.next;
            }
            current.next = null;//删除最后一个节点
            size--;//链表大小-1
            return;
        }
        //要删除的链表在中间
        Node current = head;//当前节点是头结点
        for(int i = 0 ; i < index - 1 ; i++){//遍历到当前节点的上一个节点
            current = current.next;
        }
        //将上一个节点的指针指向下下个节点
        current.next = current.next.next;
        //链表大小-1
        size--;
        return;
    }
}

双指针技巧

让我们从一个经典问题开始：

给定一个链表，判断链表中是否有环。

你可能已经使用哈希表提出了解决方案。但是，使用双指针技巧有一个更有效的解决方案。在阅读接下来的内容之前，试着自己仔细考虑一下。

想象一下，有两个速度不同的跑步者。如果他们在直路上行驶，快跑者将首先到达目的地。但是，如果它们在圆形跑道上跑步，那么快跑者如果继续跑步就会追上慢跑者。

这正是我们在链表中使用两个速度不同的指针时会遇到的情况：

如果没有环，快指针将停在链表的末尾。
如果有环，快指针最终将与慢指针相遇。
所以剩下的问题是：

这两个指针的适当速度应该是多少？

一个安全的选择是每次移动慢指针一步，而移动快指针两步。每一次迭代，快速指针将额外移动一步。如果环的长度为 M，经过 M 次迭代后，快指针肯定会多绕环一周，并赶上慢指针。

那其他选择呢？它们有用吗？它们会更高效吗？

例题1：环形链表

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

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

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

image-20250303160358855

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

image-20250303160656040

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

image-20250303160725455

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

提示：

  • 链表中节点的数目范围是 [0, 104]
  • -105 <= Node.val <= 105
  • pos 为 -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.
 * class ListNode {
 *     int val; 节点的值
 *     ListNode next; 节点下一个
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        //使用双指针
        ListNode fast = head;
        ListNode slow = head;
        if(fast == null){
            return false;
        }
        while(fast.next != null){
            fast = fast.next.next;
            slow = slow.next;

            if(fast == null){
                return false;
            }
            if(fast == slow){
                return true;
            }
        }
        // 没有环
        return false;
    }
}

例题2：环形链表2

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

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

不允许修改 链表。

image-20250303165148947

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

image-20250303165549637

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

image-20250303165605731

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

提示：

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

142. 环形链表 II - 力扣（LeetCode） 答案解释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while (true) {
            if (fast == null || fast.next == null) return null;
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) break;
        }
        fast = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }
}

例题3：相交链表

链表 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

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

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

image-20250303201954559

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

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

暴力想法：两个指针如果两个指针相同那么相交否则不相交

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
/**
 * Definition for singly-linked list.
 * 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 slow = headA;
        ListNode fast = headB;
        if(slow ==  fast){
            return slow;
        }
        
        while(slow != fast){
            while(fast != null){
                if(fast == slow){
                    return slow;
                }
                fast = fast.next;
            }
            fast = headB;
            slow = slow.next;
            if(slow == null){
                return null;
            }
        }
        if(slow == fast){
            return slow;
        }
        return null;
    }
}

image-20250304004000470

所以当到了空的时候换一条继续走就能在c1相遇了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for singly-linked list.
 * 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 = headA;
        ListNode q = headB;
        while (p != q) {
            p = p != null ? p.next : headB;
            q = q != null ? q.next : headA;
        }
        return p;
    }
}

例题4：删除链表的倒数第N个节点

链表 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

给你一个链表，删除链表的倒数第 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
/**
 * 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; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int size = 0;
        ListNode current = head;
        ListNode newHead = new ListNode(0,head);
        
        while(current != null){
            current = current.next;
            size++;
        }
        current = head;
        int target = size - n;//定位位置
        if(target == 0){
            newHead.next = current.next;
            return newHead.next;
        }
        while(target > 1){
            target--;
            current = current.next;
        }
        current.next = current.next.next;
        return newHead.next;
    }
}

经典问题

反转链表

一种解决方案是按原始顺序迭代结点，并将它们逐个移动到列表的头部。似乎很难理解。我们先用一个例子来说明我们的算法。

算法概述

image-20250304021944528

在该算法中，每个结点只移动一次。

因此，时间复杂度为 O(N)，其中 N 是链表的长度。我们只使用常量级的额外空间，所以空间复杂度为 O(1)。

例题1：翻转链表

链表 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

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

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
/**
 * 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; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null){
            return head;
        }
        
        ListNode current = head;
        ListNode pre = null;
        ListNode next = null;
        while(current != null){
            next = current.next;
            current.next = pre;
            pre = current;
            current = next;
        }
        return pre;
    }
}

image-20250304032341950

例题2：移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

链表 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

思路：先用一个哑巴新节点指向头结点，哑巴节点是当前节点

现在第一个节点变成新的节点并且保证不相等。

然后如果头结点的下一个的值相等，那么节点就指向下下一个，直到节点的下一个指向空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        // 创建一个哑节点，指向头节点
        ListNode dummy = new ListNode(0, head);
        ListNode cur = dummy; // cur 从哑节点开始

        // 遍历链表
        while (cur.next != null) {
            if (cur.next.val == val) {
                // 如果下一个节点的值等于 val，跳过该节点
                cur.next = cur.next.next;
            } else {
                // 否则，移动到下一个节点
                cur = cur.next;
            }
        }

        // 返回哑节点的下一个节点（即新链表的头节点）
        return dummy.next;
    }
}

例题3：奇偶链表

链表 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。

第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。

请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。

你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。

思路：用一个i控制奇偶，用一个节点控制偶数节点的当前节点，再用一个哑巴节点指向奇数节点，再用一个节点控制奇数节点的当前节点。

，如果是偶数，那么哑巴节点会指向下一个节点，

如果是奇数，那么当前节点会指向下下一个节点。

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; }
 * }
 */
class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode odd = head; // 奇数节点
        ListNode even = head.next; // 偶数节点
        ListNode evenHead = even; // 偶数链表的头节点

        // 分离奇数节点和偶数节点
        while (even != null && even.next != null) {
            odd.next = even.next; // 奇数节点的 next 指向下一个奇数节点
            odd = odd.next; // 移动到下一个奇数节点
            even.next = odd.next; // 偶数节点的 next 指向下一个偶数节点
            even = even.next; // 移动到下一个偶数节点
        }

        // 将奇数链表的尾节点连接到偶数链表的头节点
        odd.next = evenHead;

        return head;
    }
}

例题4：回文链表

链表 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

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

思路：

  1. 快慢指针找中点：
    • 使用快慢指针找到链表中点。快指针每次走两步，慢指针每次走一步。
    • 当快指针到达链表末尾时，慢指针指向链表中点（对于奇数长度链表，慢指针指向中间节点；对于偶数长度链表，慢指针指向后半部分的第一个节点）。
  2. 反转后半部分链表：
    • 从中点开始，反转后半部分链表。
    • 使用 prev、current 和 next 三个指针实现反转。
  3. 比较前半部分和反转后的后半部分：
    • 使用两个指针 p1 和 p2，分别指向前半部分和反转后的后半部分。
    • 逐个比较节点的值，如果不相等，则链表不是回文链表。
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 Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }

        // 快慢指针找到链表中点
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 反转后半部分链表
        ListNode prev = null;
        ListNode current = slow;
        while (current != null) {
            ListNode next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }

        // 比较前半部分和反转后的后半部分
        ListNode p1 = head;
        ListNode p2 = prev;
        while (p2 != null) {
            if (p1.val != p2.val) {
                return false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }

        return true;
    }
}

双链表

定义

双链表以类似的方式工作，但还有一个引用字段，称为“prev”字段。有了这个额外的字段，您就能够知道当前结点的前一个结点。

让我们看一个例子：

image-20250306202120801

结点结构

下面是双链表中结点结构的典型定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
// 定义节点类
class Node {
    int data;       // 数据域
    Node prev;      // 前驱指针
    Node next;      // 后继指针

    // 构造函数
    public Node(int data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

与单链接列表类似，我们将使用头结点来表示整个列表。

操作
与单链表类似，我们将介绍在双链表中如何访问数据、插入新结点或删除现有结点。

我们可以与单链表相同的方式访问数据：

我们不能在常量级的时间内访问随机位置。
我们必须从头部遍历才能得到我们想要的第一个结点。
在最坏的情况下，时间复杂度将是 O(N)，其中 N 是链表的长度。

添加操作 - 双链表

如果我们想在现有的结点 prev 之后插入一个新的结点 cur，我们可以将此过程分为两个步骤：

1、链接 cur 与 prev 和 next，其中 next 是 prev 原始的下一个节点；

image-20250306202342720

2、用 cur 重新链接 prev 和 next。

image-20250306202505213

与单链表类似，添加操作的时间和空间复杂度都是 O(1)。

如果我们想在开头或结尾插入一个新结点怎么办？

双链表结尾加入新节点步骤：
1、原end节点的next指针指向新加入节点cur;
2、新加入节点cur的prev指向原end节点，next指向null；
3、将新加入的cur节点设为末尾节点；

双链表开头加入新阶段步骤：
1、原head节点的prev指向新加入节点cur;
2、新加入节点cur的next指向原head节点；
3、cur节点设为头节点

删除操作 - 双链表

如果我们想从双链表中删除一个现有的结点 cur，我们可以简单地将它的前一个结点 prev 与下一个结点 next 链接起来。

与单链表不同，使用“prev”字段可以很容易地在常量时间内获得前一个结点。

因为我们不再需要遍历链表来获取前一个结点，所以时间和空间复杂度都是O(1)。

示例

image-20250306202749870

我们的目标是从双链表中删除结点 6。

因此，我们将它的前一个结点 23 和下一个结点 15 链接起来：

image-20250306202809617

结点 6 现在不在我们的双链表中。

如果我们要删除第一个结点或最后一个结点怎么办？

双链表删除第一个节点步骤：

1、将头结点的下一个节点设置为头结点

2、原头结点的下一个节点的prev指向null

3、原头结点的next指向null

删除最后一个节点的步骤：

  1. 将尾节点的前一个节点设置为新的尾节点：将 tail 指针指向当前尾节点的前一个节点（即 tail.prev）。
  2. 将新尾节点的 next 指针设置为 null：断开新尾节点与旧尾节点的连接。
  3. 将旧尾节点的 prev 指针设置为 null：断开旧尾节点与新尾节点的连接，便于垃圾回收。
  4. 如果链表只有一个节点：如果链表中只有一个节点，删除后需要将 head 和 tail 都设置为 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
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
// 定义节点类
class Node {
    int val;       // 数据域
    Node pre;      // 前驱指针
    Node next;     // 后继指针

    // 构造函数
    public Node(int val) {
        this.val = val;
        this.pre = null;
        this.next = null;
    }
}

class MyLinkedList {

    private Node head; // 头节点
    private Node tail; // 尾节点（方便尾部操作）
    private int size;  // 链表大小

    // 构造函数
    public MyLinkedList() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    // 获取指定下标的节点值
    public int get(int index) {
        if (index < 0 || index >= size) { // 检查下标是否合法
            return -1;
        }
        Node cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur.val;
    }

    // 在头部添加节点
    public void addAtHead(int val) {
        Node newNode = new Node(val);
        if (size == 0) { // 如果链表为空
            head = newNode;
            tail = newNode;
        } else {
            newNode.next = head; // 新节点的后继指针指向当前头节点
            head.pre = newNode;   // 当前头节点的前驱指针指向新节点
            head = newNode;       // 更新头节点为新节点
        }
        size++;
    }

    // 在尾部添加节点
    public void addAtTail(int val) {
        Node newNode = new Node(val);
        if (size == 0) { // 如果链表为空
            head = newNode;
            tail = newNode;
        } else {
            tail.next = newNode; // 当前尾节点的后继指针指向新节点
            newNode.pre = tail;   // 新节点的前驱指针指向当前尾节点
            tail = newNode;      // 更新尾节点为新节点
        }
        size++;
    }

    // 在指定下标插入节点
    public void addAtIndex(int index, int val) {
        if (index < 0 || index > size) { // 检查下标是否合法
            return;
        }
        if (index == 0) {
            addAtHead(val); // 如果插入位置是头部
        } else if (index == size) {
            addAtTail(val); // 如果插入位置是尾部
        } else {
            Node newNode = new Node(val);
            Node cur = head;
            for (int i = 0; i < index; i++) {
                cur = cur.next; // 找到插入位置的前一个节点
            }
            // 调整指针
            newNode.next = cur;
            newNode.pre = cur.pre;
            cur.pre.next = newNode;
            cur.pre = newNode;
            size++;
        }
    }

    // 删除指定下标的节点
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) { // 检查下标是否合法
            return;
        }
        if (size == 1) { // 如果链表只有一个节点
            head = null;
            tail = null;
        } else if (index == 0) { // 如果删除的是头节点
            head = head.next;
            head.pre = null;
        } else if (index == size - 1) { // 如果删除的是尾节点
            tail = tail.pre;
            tail.next = null;
        } else { // 删除中间节点
            Node cur = head;
            for (int i = 0; i < index; i++) {
                cur = cur.next;
            }
            cur.pre.next = cur.next;
            cur.next.pre = cur.pre;
        }
        size--;
    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */

小结

例题1：合并两个有序链表

链表 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

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

输入：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 均按 非递减顺序 排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(); // 用哨兵节点简化代码逻辑
        ListNode cur = dummy; // cur 指向新链表的末尾
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                cur.next = list1; // 把 list1 加到新链表中
                list1 = list1.next;
            } else { // 注：相等的情况加哪个节点都是可以的
                cur.next = list2; // 把 list2 加到新链表中
                list2 = list2.next;
            }
            cur = cur.next;
        }
        cur.next = list1 != null ? list1 : list2; // 拼接剩余链表
        return dummy.next;
    }
}


例题2：两数相加

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

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

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

输入：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]

思路：用一个新链表存储，用一个carry记录进位情况，然后用一个sum记录总和，再用%10记录录入到节点的数

小技巧：对于链表问题，返回结果为头结点时，通常需要先初始化一个预先指针 pre，该指针的下一个节点指向真正的头结点 head。使用预先指针的目的在于链表初始化时无可用节点值，而且链表构造过程需要指针移动，进而会导致头指针丢失，无法返回结果。

这个pre全过程是不会动的。

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode pre = new ListNode(0);
        ListNode cur = pre;
        int carry = 0;
        while(l1 != null || l2 != null){
            int x = l1 == null ? 0 : l1.val;
            int y = l2 == null ? 0 : l2.val;
            int sum = x + y + carry;
            carry = sum / 10;
            sum = sum % 10;
            cur.next = new ListNode(sum);

            cur = cur.next;
            if(l1 != null)
                l1 = l1.next;
            if(l2 != null)
                l2 = l2.next;
        }
        if(carry == 1) {
            cur.next = new ListNode(carry);
        }
        return pre.next;
    }
}


例题3：扁平化多级双向链表

你会得到一个双链表，其中包含的节点有一个下一个指针、一个前一个指针和一个额外的 子指针 。这个子指针可能指向一个单独的双向链表，也包含这些特殊的节点。这些子列表可以有一个或多个自己的子列表，以此类推，以生成如下面的示例所示的 多层数据结构 。

给定链表的头节点 head ，将链表 扁平化 ，以便所有节点都出现在单层双链表中。让 curr 是一个带有子列表的节点。子列表中的节点应该出现在扁平化列表中的 curr 之后 和 curr.next 之前 。

返回 扁平列表的 head 。列表中的节点必须将其 所有 子指针设置为 null 。

image-20250308114328779

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
/*
// 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) {
        Node dummy = new Node(0);
        dummy.next = head;
        while (head != null) {
            if (head.child == null) {
                head = head.next;
            } else {
                Node tmp = head.next;
                Node chead = flatten(head.child);
                head.next = chead;
                chead.prev = head;
                head.child = null;
                while (head.next != null) head = head.next;
                head.next = tmp;
                if (tmp != null) tmp.prev = head;
                head = tmp;
            }
        }
        return dummy.next;
    }
}

  • 步骤 1：保存当前节点的下一个节点 tmp，以便后续连接。
  • 步骤 2：递归调用 flatten 方法，将子链表扁平化，并返回子链表的头节点 chead。
  • 步骤 3：将当前节点的 next 指向子链表的头节点 chead，并将 chead 的 prev 指向当前节点。
  • 步骤 4：将当前节点的 child 指针置为 null，表示子链表已经被处理。
  • 步骤 5：遍历到子链表的末尾，找到子链表的最后一个节点。
  • 步骤 6：将子链表的最后一个节点的 next 指向之前保存的 tmp，并将 tmp 的 prev 指向子链表的最后一个节点。
  • 步骤 7：将 head 移动到 tmp，继续处理后续节点。

例题4：复制带随机指针的链表

链表 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

给你一个长度为 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
2
3
4
5
6
7
8
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

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

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

深拷贝 vs 浅拷贝

  1. 浅拷贝（Shallow Copy）：
    • 只复制对象的顶层结构，不会复制嵌套的对象或数据结构。
    • 如果对象包含引用类型的字段（如数组、列表、其他对象等），浅拷贝会复制引用，而不是引用的对象本身。
    • 修改新对象的引用类型字段会影响原始对象。
  2. 深拷贝（Deep Copy）：
    • 递归地复制对象的所有内容，包括嵌套的对象或数据结构。
    • 新对象与原始对象完全独立，修改新对象不会影响原始对象。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public Node copyRandomList(Node head) {
        Node cur = head;
        Node dum = new Node(0), pre = dum;
        while(cur != null) {
            Node node = new Node(cur.val); // 复制节点 cur
            pre.next = node;               // 新链表的 前驱节点 -> 当前节点
            // pre.random = "???";         // 新链表的 「 前驱节点 -> 当前节点 」 无法确定
            cur = cur.next;                // 遍历下一节点
            pre = node;                    // 保存当前新节点
        }
        return dum.next;
    }
}

方法一：哈希表
利用哈希表的查询特点，考虑构建 原链表节点 和 新链表对应节点 的键值对映射关系，再遍历构建新链表各节点的 next 和 random 引用指向即可。

算法流程：
若头节点 head 为空节点，直接返回 null 。
初始化： 哈希表 dic ， 节点 cur 指向头节点。
复制链表：
建立新节点，并向 dic 添加键值对 (原 cur 节点, 新 cur 节点） 。
cur 遍历至原链表下一节点。
构建新链表的引用指向：
构建新节点的 next 和 random 引用指向。
cur 遍历至原链表下一节点。
返回值： 新链表的头节点 dic[cur] 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        Node cur = head;
        Map<Node, Node> map = new HashMap<>();
        // 3. 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射
        while(cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        // 4. 构建新链表的 next 和 random 指向
        while(cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        // 5. 返回新链表的头节点
        return map.get(head);
    }
}


例题5：旋转链表

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

image-20250309143558654

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
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        // 边界条件：链表为空或只有一个节点，直接返回
        if (head == null || head.next == null || k == 0) {
            return head;
        }

        // 计算链表长度
        int length = 1;
        ListNode tail = head;
        while (tail.next != null) {
            tail = tail.next;
            length++;
        }

        // 计算实际需要旋转的次数
        k = k % length;
        if (k == 0) {
            return head; // 如果 k 是链表长度的倍数，直接返回
        }

        // 找到新链表的尾节点
        ListNode newTail = head;
        for (int i = 0; i < length - k - 1; i++) {
            newTail = newTail.next;
        }

        // 旋转链表
        ListNode newHead = newTail.next;
        newTail.next = null; // 断开链表
        tail.next = head; // 连接链表

        return newHead;
    }
}

链表常用API

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
// LinkedList常用方法：LinkedList 是 Java 集合框架中的一个双向链表实现，提供了丰富的 API 来操作链表。
// 增加 
// addFirst(E e) addLast(E e)
// offer(E e)  在链表尾部插入元素（队列操作） offerFirst(E e) offerLast(E e) 。
// 删除 
// poll() 删除并返回链表头部元素（队列操作）
// pollFirst() pollLast()  ---》JDK1.6以后新出的方法，提高了代码的健壮性
// removeFirst() removeLast()
//查看 element() 返回链表头部元素（不删除）
//getFirst()  getLast()
//indexOf(Object o)   lastIndexOf(Object o)
//peek() 返回链表头部元素（不删除，队列操作）
//peekFirst() peekLast()
 
//LinkedList可以添加重复数据
// list.clear();//清空集合
//普通for循环：
for(int i = 0;i<list.size();i++){
    System.out.println(list.get(i));
}

//增强for：
for(String s:list){
    System.out.println(s);
}

//迭代器：
/*Iterator<String> it = list.iterator();
        while(it.hasNext()){
            System.out.println(it.next());
        }*/
//下面这种方式好，节省内存
for(Iterator<String> it = list.iterator();it.hasNext();){
    System.out.println(it.next());