链表习题解析
洪笳淏 Lv4
 2021-09-24 20:10:00      

链表高频题目

2. 两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

avatar

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

示例 2：

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

示例 3：

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

提示：

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

解题思路：

  本题很自然的就想到先将两个链表保存的数都转化成变量的形式存储下来，直接相加后再逐位用链表保存后输出。但是，在提交代码后，发现其中一个测试用例没有通过。原来是其中一个链表转换成数字变量后，它直接溢出了，导致出错。所以要完全AC这道题，这种方法肯定是不行的。

  由于输入的两个链表都是逆序存储数字的位数的，因此两个链表中同一位置的数字可以直接相加。我们同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加。具体而言，如果当前两个链表处相应位置的数字为n1,n2，进位值为carry，他们的和为n1+n2+carry，其中答案链表处相应位置的数字为(n1+n2+carry)%10，而新的进位值为(n1+n2+carry)/10。

  如果两个链表的长度不同，则可以认为长度短的链表的后面有若干个 0 。此外，如果链表遍历结束后，有 carry>0，还需要在答案链表的后面附加一个节点，节点的值为 carry。

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
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    carry := 0
    v := 0
    h1 := l1	// 保存头节点
    f1 := l1	// 记录前一节点，方便拼接
    for l1 != nil && l2 != nil {	// 当l1和l2都没有遍历到表尾
        v = (l1.Val+l2.Val+carry)%10	// 值
        carry = (l1.Val+l2.Val+carry)/10   //	进位
        l1.Val = v		//	保存到l1中（直接替换掉这个位置节点的值）
        f1 = l1			//	f1跟进
        l1 = l1.Next	//	l1指向其Next
        l2 = l2.Next	//	l2指向其Next
    }

    if l1 == nil && l2 == nil && carry != 0 {	// l1和l2等长且最后还有一位进位
        f1.Next = &ListNode{	// 创造一个节点，其值为进位值
            Val     :       carry,
            Next    :       nil,
        }
    }

    if l1 != nil {	//	l1更长，处理完l1剩余的节点
        for l1 != nil {
            v = (l1.Val+carry)%10
            carry = (l1.Val+carry)/10        
            l1.Val = v
            f1 = l1
            l1 = l1.Next
        }
        if carry != 0 {	//	考虑最后是否有进位
            f1.Next = &ListNode{
                Val     :       carry,
                Next    :       nil,
            }
        }
    }

    if l2 != nil {	//	l2更长，处理完l2剩余的节点
        f1.Next = l2
        for l2 != nil {
            v = (l2.Val+carry)%10
            carry = (l2.Val+carry)/10     
            l2.Val = v
            f1 = l2
            l2 = l2.Next
        }
        if carry != 0 {	//	考虑最后是否有进位
            f1.Next = &ListNode{
                Val     :       carry,
                Next    :       nil,
            }
        }
    }
    return h1
}

合并链表

21. 合并两个有序链表

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

示例 1：

avatar

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

示例 2：

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

示例 3：

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

提示：

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

这题思路很简单，用下图就可以概括：

avatar

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
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    dummy := &ListNode{Val:0,Next:nil,}
    tail := dummy
    var node *ListNode

    for l1 != nil && l2 != nil {
        if l1.Val <= l2.Val {
            node = &ListNode{
                Val     :   l1.Val,
                Next    :   nil,
            }
            l1 = l1.Next
        } else {
            node = &ListNode{
                Val     :   l2.Val,
                Next    :   nil,
            }
            l2 = l2.Next
        }
        tail.Next = node
        tail = node
    }

    if l1 != nil {
        tail.Next = l1
    }
    if l2 != nil {
        tail.Next = l2
    }
    return dummy.Next
}

23. 合并K个升序链表

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • k == 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

解题思路：

  将每个链表的节点分别填充入最小堆中，就可以实现所有节点数值的升序排列。最小堆的实现参考我的另一篇文章二叉堆的Go语言实现。

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
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
import "container/heap"
type IntHeap []int

func (h IntHeap) Len() int {
    return len(h)
}

func (h IntHeap) Less(i,j int) bool {
    return h[i]<h[j]
}

func (h IntHeap) Swap(i,j int) {
    h[i], h[j] = h[j], h[i]
}

func (h *IntHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(*h)
    x := old[n-1]
    *h = old[:n-1]
    return x
}


func mergeKLists(lists []*ListNode) *ListNode {
    l := len(lists)
    if l == 0 {
        return nil
    }
    h := &IntHeap{}
    for i:=0; i<l; i++ {
        if lists[i] == nil {
            continue
        }
        node := lists[i]
        for node != nil {
            *h = append(*h, node.Val)
            node = node.Next
        }
    }
    if h.Len() == 0 {
        return nil
    }
    heap.Init(h)

    head := &ListNode{
        Val     :       (*h)[0],
        Next    :       nil,
    }
    t := head
    heap.Pop(h)
    for h.Len() > 0 {
        x := heap.Pop(h).(int)
        node := &ListNode{
            Val     :       x,
            Next    :       nil,
        }
        t.Next = node
        t = node
    }

    return head
}

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

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

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

示例 1：

avatat

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

解题思路：

  这个逻辑就很简单了，要删除倒数第 n 个节点，就得获得倒数第 n + 1 个节点的引用，首先，我们先让一个指针 p1 指向链表的头节点 head，然后走 k 步：

avatar

现在的 p1，只要再走 n - k 步，就能走到链表末尾的空指针了对吧？

趁这个时候，再用一个指针 p2 指向链表头节点 head：

avatar

接下来就很显然了，让 p1 和 p2 同时向前走，p1 走到链表末尾的空指针时走了 n - k 步，p2 也走了 n - k 步，也就是链表的倒数第 k 个节点：

avatar

这样，只遍历了一次链表，就获得了倒数第 k 个节点 p2。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    fast, slow := head, head
    for i:=0; i<n; i++ {
        fast = fast.Next
    }
    if fast == nil {	//fast指向nil，说明n=链表的节点数，即删除第一个节点
        return head.Next
    }

    for fast.Next != nil {	// 定位到要删除节点的前一个节点
        fast = fast.Next
        slow = slow.Next
    }
    slow.Next = slow.Next.Next
    return head
}

160. 相交链表

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

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

avatar

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

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

示例 1：

avatar

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

avatar

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

avatar

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

解题思路：

  这个题直接的想法可能是用 HashSet 记录一个链表的所有节点，然后和另一条链表对比，但这就需要额外的空间。

  如果不用额外的空间，只使用两个指针，你如何做呢？难点在于，由于两条链表的长度可能不同，两条链表之间的节点无法对应：

avatar

  如果用两个指针 p1 和 p2 分别在两条链表上前进，并不能同时走到公共节点，也就无法得到相交节点 c1。

  所以，解决这个问题的关键是，通过某些方式，让 p1 和 p2 能够同时到达相交节点 **c1**。

  所以，我们可以让 p1 遍历完链表 A 之后开始遍历链表 B，让 p2 遍历完链表 B 之后开始遍历链表 A，这样相当于「逻辑上」两条链表接在了一起。如果这样进行拼接，就可以让 p1 和 p2 同时进入公共部分，也就是同时到达相交节点 c1：

avatar

  那你可能会问，如果说两个链表没有相交点，是否能够正确的返回 nil 呢？这个逻辑可以覆盖这种情况的，相当于 c1 节点是 nil 空指针嘛，可以正确返回 nil。

按照这个思路，可以写出如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    a, b := headA, headB
    for a != b {
        if a != nil {
            a = a.Next
        } else {
            a = headB
        }

        if b != nil {
            b = b.Next
        } else {
            b = headA
        }
    }
    return a
}

这样，这道题就解决了，空间复杂度为 O(1)，时间复杂度为 O(N)。

反转链表

反转整个链表

  • 递归
1
2
3
4
5
6
7
8
9
func reverse(head *ListNode) *ListNode {
    if head.Next == nil {	// 递归出口
        return head
    }
    last := reverse(head.Next)
    head.Next.Next = head
    head.Next = nil
    return last
}
  • 迭代
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func reverse(head *ListNode) *ListNode {
    first := head.Next.Next
    second := head.Next
    third := head
    head.Next = nil
    for first != nil {
        second.Next = third
        third = second
        second = first
        first = first.Next
    }
    second.Next = third
    return second
}

反转链表前n个节点

  比如说对于下图链表，执行 reverseN(head, 3)：

avatar

  • 递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var successor *ListNode	// 后驱节点
successor = nil

func reverseN(head *ListNode, n int) *ListNode {
    if n == 1 {
        successor = head.Next
        return head
    }
    
    last := reverseN(head.Next,n-1)
    
    head.Next.Next = head
    head.Next = successor
    return last
}
  • 迭代
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func reverseN(head *ListNode, n int) *ListNode {
    first := head.Next.Next
    second := head.Next
    third := head
    
    if n == 1 {		// n=1,不需要翻转
        return head
    }
    if n == 2 {		// n=2,直接翻转前两个节点即可
        second.Next = third
        third.Next = first
        return second
    }
    for n-2 > 0 {	// n>2时的情况，结合上图来推一遍会比较清晰
        second.Next = third
        third = second
        second = first
        first = first.Next
        n--
    }
    second.Next = third
    third.Next = first
    return second
}

反转链表的一部分

  给一个索引区间 [m,n]（索引从 1 开始），仅仅反转区间中的链表元素。

  • 递归
1
2
3
4
5
6
7
8
func reverseBetween(head *ListNode, m,n int) *ListNode {
    if m == 1 {	// base case
        return reverseN(head,n)	// 相当于反转前n个元素
    }
    // 前进到反转的起点触发 base case
    head.Next = reverseBetween(head.Next, m-1, n-1)
    return head
}
  • 迭代

92. 反转链表 II

示例 1：

avatar

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

示例 2：

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

提示：

  • 链表中节点数目为 n
  • 1 <= n <= 500
  • -500 <= Node.val <= 500
  • 1 <= left <= right <= n

解题思路：

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

avatar

  反转 left 到 right 部分以后，再拼接起来。我们还需要记录 left的前一个节点，和 right 的后一个节点。如图所示：

avatar

  • 第 1 步：先将待反转的区域反转；
  • 第 2 步：把 pre 的 next 指针指向反转以后的链表头节点，把反转以后的链表的尾节点的 next 指针指向 succ
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
func reverseBetween(head *ListNode, left int, right int) *ListNode {
    dummyNode := &ListNode{Val:-1}
    dummyNode.Next = head
    pre := dummyNode
    
    // 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点
    for i:=0; i<left-1; i++ {
        pre = pre.Next
    }
    
    // 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点
    rightNode := pre
    for i := 0; i < right-left+1; i++ {
        rightNode = rightNode.Next
    }
    
    // 第 3 步：切断出一个子链表（截取链表）
    leftNode := pre.Next;
    curr := rightNode.Next;
    
    // 注意：切断链接
    pre.Next = nil
    rightNode.Next = nil
	
    // 第4步：反转区间
    reverse(leftNode)
    
    // 第 5 步：接回到原来的链表中
    pre.Next = rightNode
    leftNode.Next = curr
    return dummyNode.Next
}

如何判断回文链表

234. 回文链表

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

示例 1：

avatar

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

示例 2：

avatar

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

提示：

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

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

解题思路：

  最一般的做法是先用一个数组将整个链表存储下来，再从数组的两端向中间逼近来判断是否是回文串。进阶要求是用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题。

  先通过快慢指针翻转后半部分链表（注意分情况讨论奇数和偶数）。然后翻转后半部分链表（如果是奇数链表，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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func isPalindrome(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return true
    }

    fast, slow := head, head
    for fast != nil && fast.Next != nil {	// 找到链表的中间位置
        fast = fast.Next.Next
        slow = slow.Next
    } 

    if fast == nil {  // 偶数串，slow指向后半部分的第一个节点处
        backHead := reverse(slow)
        for backHead != nil {
            if backHead.Val != head.Val {
                return false
            }
            backHead = backHead.Next
            head = head.Next
        }
    } else {	// 奇数串，slow指向前后两段的正中间
        slow = slow.Next
        backHead := reverse(slow)
        for backHead != nil {
             if backHead.Val != head.Val {
                return false
            }
            backHead = backHead.Next
            head = head.Next
        }
    }
    return true
}

func reverse(head *ListNode) *ListNode {
    pre, cur := head, head.Next
    for cur != nil {
        nxt := cur.Next
        cur.Next = pre
        pre = cur
        cur = nxt
    }
    head.Next = nil
    return pre
}
  • Post title：链表习题解析
  • Post author：洪笳淏
  • Create time：2021-09-24 20:10:00
  • Post link：https://jiahaohong1997.github.io/2021/09/24/链表习题解析/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.
 Comments