链表集合
Yuxuan Wu Lv13
2021-06-21 21:18:13 6.8k Words 29 Mins

设计链表

单链表

设计链表的实现。您可以选择使用单链表或双链表。

img

  • 单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。
  • 双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

在链表类中实现这些功能：

get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

单链表结点的实现

1
2
3
4
5
6
7
public class SinglyListNode {
    int val;
    SinglyListNode next;
    SinglyListNode(int x) { 
      this.val = x; 
    }
}
  • 一个值
  • 一个引用字段

Leetcode 上的测试代码

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
package linear;

public class ListNode {
    int val;
    ListNode next;

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

    // 链表节点的构造函数
    // 使用arr为参数，创建一个链表，当前的ListNode为链表头节点
    public ListNode(int[] arr) throws Exception {
        if (arr == null || arr.length == 0)
            throw new Exception("arr can not be empty");

        this.val = arr[0];
        ListNode cur = this;
        for (int i = 1; i < arr.length; i++) {
            cur.next = new ListNode(arr[i]);
            cur = cur.next;
        }
    }

    //以当前节点为头节点的链表信息字符串 方便查看
    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        ListNode cur = this;
        while (cur != null) {
            res.append(cur.val + "->");
            cur = cur.next;
        }
        res.append("NULL");
        return res.toString();
    }
}
  • 创建ListNode结点类（核心一个存value，一个存引用地址）
  • 构造参数，以接受不同的输入 （这里核心是需要接收Array的格式，然后将值转换成链表）
  • 重写toString 的方法，以适合打印print

结果

1
2
3
4
5
2->4->3->NULL

5->6->4->NULL

7->0->8->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
class MyLinkedList {
    class Node{
        int val;
        Node next;
        Node(int val) {
            this.val = val;
        }
    }

    int size;
    Node head; 
    /** Initialize your data structure here. */
    public MyLinkedList() {
        this.size = 0;
        this.head = null;

    }
    
    /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
    public int get(int index) {
        if(index <0 || index >= size|| head == null){
            return -1;
        }
        Node temp = this.head;
        for (int i = 0; i<index; i++){
            temp = temp.next;
        }
        return temp.val;
    }
    
    /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
    public void addAtHead(int val) {
        Node node = new Node (val);
        node.next= this.head;
        this.head = node;
        size ++;
    }
    
    /** Append a node of value val to the last element of the linked list. */
    public void addAtTail(int val){
        if (size==0){
            this.head = new Node (val);
            head.next= null;
            size++;
        }else{
            Node temp = this.head;
            while (temp.next!=null){
                temp = temp.next;
            }
            Node tail = new Node(val);
            tail.next =null;
            temp.next =tail;
            size++;
        }
    }
    
    /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
    public void addAtIndex(int index, int val) {
        if (index>this.size){
            return;
        }

        if (index<=0){
            addAtHead(val);
            return;
        }

        if (index==this.size){
            addAtTail(val);
            return;
        }

        Node temp = this.head;
        for (int i = 0; i <index-1;i++){
            temp = temp.next;
        }

        Node insertNode = new Node(val);
        insertNode.next = temp.next;
        temp.next = insertNode;
        size ++;

    }
    
    /** Delete the index-th node in the linked list, if the index is valid. */
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= this.size) {
            return;
        }
        if (index == 0) {
            if (size != 1) {
                Node temp = this.head.next;
                this.head =temp;
                size--;
                return;
            }else {
                this.head = null;
                size--;
                return;
            }
        }
        Node temp = this.head;
        for (int i = 0; i < index - 1; i++) {
            temp = temp.next;
        }
        Node deleteNode = temp.next;
        temp.next = deleteNode.next;
        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);
 */

Reference:
链接：https://leetcode-cn.com/leetbook/read/linked-list/jy291/
来源：力扣（LeetCode）

LeetCode 算法实战

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

难度中等1424收藏分享切换为英文接收动态反馈

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

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

示例 1：

img

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]

提示：

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

方法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
public ListNode removeNthFromEnd(ListNode head, int n) {
        // 1. 定义dummyNode,便于后来的插入和操作，返回一整条链表
        ListNode dummyNode = new ListNode(0,head);

        // 2. 先算出链表的长度
        int length = getNodeLength(head);

        // 3. 定义current结点
        ListNode curr = dummyNode;
        
        // 4. 循环结点到待删除节点的前一个
        int i = 0;
        while(curr.next!=null){
            if (i == length-n) break;
            curr = curr.next;
            i++;
        }
  			// 5. 执行删除操作
        curr.next = curr.next.next;
  
  			// 6. 返回dummyNode 那条链除了第一个dummyNode的
        return dummyNode.next;

    }
    public int getNodeLength(ListNode node){
            int n = 0;
      	// 7. 注意这个node！=null 而不是node.next
            while(node!=null){
                n++;
                node = node.next;
            }
            return n;
        }

方法2：双指针

p3

哑结点（dummy head）:

  • 不存储数据，这里使用的目的是保证当第一个指针走到null的时候，第二个指针正好走到了待删除结点的前一个结点，这样就可以轻松的删除，直接second = second.next.next循环到下一个去
  • 可以用来最后指定链表，否则没法最后指定返回所有的链表
    • 因为ListNode = ListNode.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
public ListNode removeNthFromEnd(ListNode head, int n) {


    // 1. 定义dummy head
    ListNode dummyHead = new ListNode(0, head);

    // 2. 定义firstNode 从head出发
    ListNode firstNode = head;

    // 3. 定义secondNode 在dummy head
    ListNode secondNode = dummyHead;

    // 4. 循环n下
    for (int i = 0; i < n; i++) {
        firstNode = firstNode.next;
    }


    // 5. secondNode 和firstNode 同时出发； 直到firstNode == null
    while (firstNode != null) {
        firstNode = firstNode.next;
        secondNode = secondNode.next;
    }

    // 6. 完成删除操作
    secondNode.next = secondNode.next.next;

    // 7. 定义一个新的完整的链表返回
    ListNode ans = dummyHead;
    ans = dummyHead.next;
    return ans;

}

160. 相交链表

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

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

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

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

示例 1：

img

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

img

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

img

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

提示：

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

注意考虑

注意以下的情况是不会出现的

但是不会出现以下相交的情况，因为每个节点只有一个 next 指针，也就只能有一个后继节点，而以下示例中节点 c 有两个后继节点。

1
2
3
4
5
A:          a1 → a2       d1 → d2
                    ↘  ↗
                      c
                    ↗  ↘
B:    b1 → b2 → b3        e1 → e2

方法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
/**
 * 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) {
        /**
        定义两个指针, 第一轮让两个到达末尾的节点指向另一个链表的头部, 最后如果相遇则为交点(在第一轮移动中恰好抹除了长度差)
        两个指针等于移动了相同的距离, 有交点就返回, 无交点就是各走了两条指针的长度
        **/
        if(headA == null || headB == null) return null;
        ListNode pA = headA, pB = headB;
        // 在这里第一轮体现在pA和pB第一次到达尾部会移向另一链表的表头
      //而第二轮体现在如果pA或pB相交就返回交点, 不相交最后就是null==null
      // 终止条件就是null==null
        while(pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}

相交链表.png

一图胜千言，看图你就明白了

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

这里使用图解的方式，解释比较巧妙的一种实现。

根据题目意思
如果两个链表相交，那么相交点之后的长度是相同的

我们需要做的事情是，让两个链表从同距离末尾同等距离的位置开始遍历。这个位置只能是较短链表的头结点位置。
为此，我们必须消除两个链表的长度差

指针 pA 指向 A 链表，指针 pB 指向 B 链表，依次往后遍历
如果 pA 到了末尾，则 pA = headB 继续遍历
如果 pB 到了末尾，则 pB = headA 继续遍历
比较长的链表指针指向较短链表head时，长度差就消除了
如此，只需要将最短链表遍历两次即可找到位置

作者：reals
链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/solution/tu-jie-xiang-jiao-lian-biao-by-user7208t/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

走到尽头见不到你，于是走过你来时的路，等到相遇时才发现，你也走过我来时的路。

可以理解成两个人速度一致， 走过的路程一致。那么肯定会同一个时间点到达终点。如果到达终点的最后一段路两人都走的话，那么这段路上俩人肯定是肩并肩手牵手的。 nb

141.环形链表I

img

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

img

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

方法1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean hasCircle(ListNode head) {
    // 这里考虑的是只有头结点和头结点为空的情况
    if (head == null || head.next == null) {
        return false;
    }
    ListNode slow = head;
    ListNode fast = head.next;
    while (slow != fast) {
        // 这里需要保证fast.next 仍然有下一个结点，所以需要进行判断
      	// 循环断开的条件是fast已经到头了，为null
      	// 因为假如没有loop，他一定会走到头，
        if (fast == null || fast.next== null) {
            return false;
        }
        slow = slow.next;
        fast = fast.next.next;
    }
    return true;
}

双指针问题，一快一慢，如果重合则会有环

  • 注意这里是快慢指针开始位置不同

细节

为什么我们要规定初始时慢指针在位置 head，快指针在位置 head.next，而不是两个指针都在位置 head（即与「乌龟」和「兔子」中的叙述相同）？

观察下面的代码，我们使用的是 while 循环，循环条件先于循环体。由于循环条件一定是判断快慢指针是否重合，如果我们将两个指针初始都置于 head (就是fast = slow = head)，那么 while 循环就不会执行。这种情况会将无环情况错误识别成有环的情况

1
2
3
4
5
6
7
8
9
10
11
输入：

[1,2] -1

输出：

true

预期结果：

false

因此，我们可以假想一个在 head 之前的虚拟节点，慢指针从虚拟节点移动一步到达 head，快指针从虚拟节点移动两步到达 head.next，这样我们就可以使用 while 循环了。当然，我们也可以使用 do-while 循环。此时，我们就可以把快慢指针的初始值都置为 head。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/linked-list-cycle/solution/huan-xing-lian-biao-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

方法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(true){
            try{
                slow = slow.next;
                fast = fast.next.next;
            }   catch (Exception e){
                return false;
            }
            if (slow == fast){
                return true;
            }
        }
    }
  • 注意这里双指针的起始位置是相同的
  • 如果位置不同，需要像方法一一样判断是否存在空指针问题

方法3 HashSet

  • 通过判断add的时候是否可以加入来返回值
1
2
3
4
5
6
7
8
public boolean hasCycle(ListNode head) {
    HashSet<ListNode> hashset = new HashSet<ListNode>();
    while(head!=null){
        if(!hashset.add(head)) return true;
        head =head.next;
    }
    return false;
}

最容易想到的方法是遍历所有节点，每次遍历到一个节点时，判断该节点此前是否被访问过。

具体地，我们可以使用哈希表来存储所有已经访问过的节点。每次我们到达一个节点，如果该节点已经存在于哈希表中，则说明该链表是环形链表，否则就将该节点加入哈希表中。重复这一过程，直到我们遍历完整个链表即可。

环形链表II

img

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

注意这里找到的其实是环结点

解题思路

1623750459597.jpg

    //下面开始找环的入口节点  
    //刚才的循环 慢指针走了a + b (a是从开始到入口节点) 假设等于cnt
    //          快指针走了 a + b + c + b (b + c = 环)，应该等于2 * cnt
    //推导出 a = c，所以把慢指针再放到头节点，下一次快慢指针相遇的节点即环的入口节点

方法1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;

    while (slow != null && fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (slow == fast) break;
    }
    //如果满足下面的条件，说明无环
    if (fast == null || fast.next == null) return null;

    //下面开始找环的入口节点
    //刚才的循环 慢指针走了a + b (a是从开始到入口节点) 假设等于cnt
    //          快指针走了 a + b + c + b (b + c = 环)，应该等于2 * cnt
    //推导出 a = c，所以把慢指针再放到头节点，下一次快慢指针相遇的节点即环的入口节点
    slow = head;
    while (slow != null && fast != null) {
        if (slow == fast) break;
        slow = slow.next;
        fast = fast.next;
    }
    return fast;
}

方法二

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
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        // 先判断是否有环，找到环的入口(双指针)
        while(true){
            try{
                slow = slow.next;
                fast = fast.next.next;
            }catch(Exception e){
                return null;
            }
            if (slow == fast){
                break;
            }
        }
        
        // 判断无环的条件 (fast==null||fast.next==null)


        // 将一个指针放到开头，然后让慢指针继续走，下次相遇的地方就是环入口
        fast = head;
        while (slow != null && fast != null) {
            if (slow == fast) break;
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }
}

203. 移除链表元素

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

示例 1：

img

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

示例 2：

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

示例 3：

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

迭代解法

来看第一种操作：直接使用原来的链表来进行移除。

此时遇到的问题就是头列表无法删除

Image

移除头结点和移除其他节点的操作是不一样的，因为链表的其他节点都是通过前一个节点来移除当前节点，而头结点没有前一个节点。

所以头结点如何移除呢，其实只要将头结点向后移动一位就可以，这样就从链表中移除了一个头结点。

Image

依然别忘将原头结点从内存中删掉。Image

这样移除了一个头结点，是不是发现，在单链表中移除头结点 和 移除其他节点的操作方式是不一样，其实在写代码的时候也会发现，需要单独写一段逻辑来处理移除头结点的情况。

所以推荐使用虚拟节点,来满足对头节点的操作

那么可不可以 以一种统一的逻辑来移除 链表的节点呢。

其实可以设置一个虚拟头结点，这样原链表的所有节点就都可以按照统一的方式进行移除了。

来看看如何设置一个虚拟头。依然还是在这个链表中，移除元素1。

Image

这里来给链表添加一个虚拟头结点为新的头结点，此时要移除这个旧头结点元素1。

这样是不是就可以使用和移除链表其他节点的方式统一了呢？

来看一下，如何移除元素1 呢，还是熟悉的方式，然后从内存中删除元素1。

最后呢在题目中，return 头结点的时候，别忘了 return dummyNode->next;， 这才是新的头结点

链表的一大问题就是操作当前节点必须要找前一个节点才能操作。这就造成了，头结点的尴尬，因为头结点没有前一个节点了。

每次对应头结点的情况都要单独处理，所以使用虚拟头结点的技巧，就可以解决这个问题。

同时需要一个curr节点来完成遍历的操作，所以需要三个node

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class RemoveElements {
    //    int[] num1 = {1, 2, 6, 3, 4, 5, 6};
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) return null;

        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode curr = dummyHead; // 如果这里改成head，则会导致在链表6，6，6的时候使第一个给保留下来,引入的dummyHead可以解决这个问题
        while (curr.next != null) {
            if (curr.next.val == val) {
                curr.next = curr.next.next;
            } else {
                curr = curr.next;
            }
        }
        return dummyHead.next;
    }
}

递归解法

递归的核心解法其实就是不停的递归比较头节点的值是否相等（可以理解为压栈和弹栈）

1
2
3
4
5
public ListNode removeElements(ListNode head, int val) {
    if (head == null) return head;
    head.next = removeElements(head.next, val);
    return head.val == val? head.next: head;
}

2. 两数相加

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

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

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

img

示例 1：

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

示例 2：

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

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法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
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 1. 定义头结点和尾结点;定义进位值
        // head 用来记录链表的头部，tail不断向后进行让链表变长
        ListNode head = null, tail = null;
        int carry = 0;

        // 2. 三元运算符来同时遍历l1,l2
        while (l1 != null || l2 != null) {
            int num1 = l1 != null ? l1.val : 0;
            int num2 = l2 != null ? l2.val : 0;
            int perSum = num1 + num2 + carry;
            if (head == null) {
                // 3. 第一次循环，构建新的链表，用来处理第一个node的和并且赋值位val
                // 注意这里因为创建列表的早，所以head即是tail
                head = tail = new ListNode(perSum % 10);
            } else {
                // 4. 注意这里不是第一次第一次循环，是第二次循环以后
                tail.next = new ListNode(perSum % 10);
                tail = tail.next;
            }

            // 5. 这里获得了进位的值，也用到了向下强转 (12/10 = 1 )
            carry = perSum / 10;

            // 6. 判断是否为最后一个结点, 保证循环
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }

            // 7. 如果链表遍历结束后进位符大于1，需要在答案链表后面附加一个结点，结点的值为carry
            if (carry > 0) {
                tail.next = new ListNode(carry);
            }
        }
        return 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
private ListNode dummyHead = new ListNode(-1);
private ListNode tail = dummyHead;

public ListNode addTwoNumbers2(ListNode l1, ListNode l2) {

    int carry = 0;
    // l1 & l2 长度相同的部分
    while (l1 != null && l2 != null) {
        int val = (l1.val + l2.val + carry) % 10;
        carry = (l1.val + l2.val + carry) / 10;
        appendNode(new ListNode(val));
        l1 = l1.next;
        l2 = l2.next;
    }
    // l1 比l2 长
    while (l1 != null) {
        int val = (l1.val + 0 + carry) % 10;
        carry = (l1.val + carry) / 10;
        appendNode(new ListNode(val));
        l1 = l1.next;
    }

    // l2 比l1 长
    while (l2 != null) {
        int val = (0 + l2.val + carry) % 10;
        carry = (l2.val + carry) / 10;
        appendNode(new ListNode(val));
        l2 = l2.next;
    }

    // 考虑最后一个进位符
    if (carry != 0) {
        appendNode(new ListNode(carry));
    }

    // 注意这里是dummyHead.next
    return dummyHead.next;
}

private void appendNode(ListNode node) {
    tail.next = node;
    tail = node;
}

这里将appendNode分开，重新定义一个方法

测试

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
package test;

import linear.AddTwoNumber;
import linear.ListNode;

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

public class AddTwoNumberTest {
    public static void main(String[] args) throws Exception {
        int[] l1Array = {2,4,3};
        int[] l2Array = {5, 6, 4};
        ListNode l1 = new ListNode(l1Array);
        ListNode l2 = new ListNode(l2Array);
        System.out.println(l1);
        System.out.println(l2);

        System.out.println("================");
        AddTwoNumber obj = new AddTwoNumber();
        ListNode results = obj.addTwoNumbers(l1, l2);
        System.out.println(results);


    }
}

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

难度中等1424收藏分享切换为英文接收动态反馈

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

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

示例 1：

img

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]

提示：

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

方法一：双指针

p3

哑结点（dummy head）:

  • 不存储数据，这里使用的目的是保证当第一个指针走到null的时候，第二个指针正好走到了待删除结点的前一个结点，这样就可以轻松的删除，直接second = second.next.next循环到下一个去
  • 可以用来最后指定链表，否则没法最后指定返回所有的链表
    • 因为ListNode = ListNode.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
public ListNode removeNthFromEnd(ListNode head, int n) {


    // 1. 定义dummy head
    ListNode dummyHead = new ListNode(0, head);

    // 2. 定义firstNode 从head出发
    ListNode firstNode = head;

    // 3. 定义secondNode 在dummy head
    ListNode secondNode = dummyHead;

    // 4. 循环n下
    for (int i = 0; i < n; i++) {
        firstNode = firstNode.next;
    }


    // 5. secondNode 和firstNode 同时出发； 直到firstNode == null
    while (firstNode != null) {
        firstNode = firstNode.next;
        secondNode = secondNode.next;
    }

    // 6. 完成删除操作
    secondNode.next = secondNode.next.next;

    // 7. 定义一个新的完整的链表返回
    ListNode ans = dummyHead;
    ans = dummyHead.next;
    return ans;

}

方法二： 计算链表的长度

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
public ListNode removeNthFromEnd(ListNode head, int n) {
        // 1. 定义dummyNode,便于后来的插入和操作，返回一整条链表
        ListNode dummyNode = new ListNode(0,head);

        // 2. 先算出链表的长度
        int length = getNodeLength(head);

        // 3. 定义current结点
        ListNode curr = dummyNode;
        
        // 4. 循环结点到待删除节点的前一个
        int i = 0;
        while(curr.next!=null){
            if (i == length-n) break;
            curr = curr.next;
            i++;
        }
  			// 5. 执行删除操作
        curr.next = curr.next.next;
  
  			// 6. 返回dummyNode 那条链除了第一个dummyNode的
        return dummyNode.next;

    }
    public int getNodeLength(ListNode node){
            int n = 0;
      	// 7. 注意这个node！=null 而不是node.next
            while(node!=null){
                n++;
                node = node.next;
            }
            return n;
        }

21. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

Example 1:

img

1
2
Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

1
2
Input: l1 = [], l2 = []
Output: []

Example 3:

1
2
Input: l1 = [], l2 = [0]
Output: [0]

方法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
        /**
         * 注意不用考虑三种情况，相等的那种，因为只要保证一个不动，另一个也肯定不动
         */
public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
        // 类似归并排序中的合并过程
        ListNode dummyHead = new ListNode(0);
        ListNode cur = dummyHead;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                cur = cur.next;
                l1 = l1.next;
            } else {
                cur.next = l2;
                cur = cur.next;
                l2 = l2.next;
            }
        }
        // 任一为空，直接连接另一条链表
        if (l1 == null) {
            cur.next = l2;
        } else {
            cur.next = l1;
        }
        return dummyHead.next;
    }

方法2（ArrayList）:

简单朴实的用arraylist来存储东西

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
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ArrayList<Integer> list1 = nodeToList(l1);
    ArrayList<Integer> list2 = nodeToList(l2);
    list1.addAll(list2);

    Object[] array = list1.toArray();
    Arrays.sort(array);

    return arrayToNode(array);
}

public ArrayList<Integer> nodeToList(ListNode node) {
    ArrayList<Integer> arraylist = new ArrayList<>();
    while (node != null) {
        arraylist.add(node.val);
        node = node.next;
    }
    return arraylist;
}

public ListNode arrayToNode(Object[] array) {
    ListNode listNode = new ListNode();
    ListNode dummyHead = new ListNode();
    dummyHead.next = listNode;

    for (int i = 0; i < array.length; i++) {
        listNode.next = new ListNode((Integer) array[i]);
        listNode = listNode.next;
    }

    return dummyHead.next.next;
}

方法一：递归
思路

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

image-20210812124329635

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

算法

我们直接将以上递归过程建模，同时需要考虑边界情况。

如果 l1 或者 l2 一开始就是空链表 ，那么没有任何操作需要合并，所以我们只需要返回非空链表。否则，我们要判断 l1 和 l2 哪一个链表的头节点的值更小，然后递归地决定下一个添加到结果里的节点。如果两个链表有一个为空，递归结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

复杂度分析

时间复杂度：O(n + m)O(n+m)，其中 nn 和 mm 分别为两个链表的长度。因为每次调用递归都会去掉 l1 或者 l2 的头节点（直到至少有一个链表为空），函数 mergeTwoList 至多只会递归调用每个节点一次。因此，时间复杂度取决于合并后的链表长度，即 O(n+m)O(n+m)。

空间复杂度：O(n + m)O(n+m)，其中 nn 和 mm 分别为两个链表的长度。递归调用 mergeTwoLists 函数时需要消耗栈空间，栈空间的大小取决于递归调用的深度。结束递归调用时 mergeTwoLists 函数最多调用 n+mn+m 次，因此空间复杂度为 O(n+m)O(n+m)。

  • Post title：链表集合
  • Post author：Yuxuan Wu
  • Create time：2021-06-21 21:18:13
  • Post link：yuxuanwu17.github.io2021/06/21/2021-06-22-链表集合/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.