单链表解题技巧

发表于 分类于
本文字数： 3.5k 阅读时长 ≈ 3 分钟

单链表是经典题型，本文列出了单链表最常出现的部分题型，并给出了每道题最合适最高效的解决方法，主要的解题方法技巧包含以下三种：

  • 双指针
  • 快慢指针
  • 最小堆
1、合并两个有序链表

依次迭代：设置一个伪头节点 preHead 用于指向返回结果的头节点，并将当前节点 cur 指向 preHead。然后对比两个链表的头节点，将 cur 的next指向更小的节点，并将该链表的头节点指向下一个节点。直到有一个链表为空，将另一个链表的剩余部分拼接到 cur 的next节点即可。最后返回伪头节点的 next 节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    preHead := &ListNode{}		// dummy节点，用于返回结果
    cur := preHead
    for l1 != nil && l2 != nil {
        if l1.Val < l2.Val {
            cur.Next = l1
            l1 = l1.Next
        } else {
            cur.Next = l2
            l2 = l2.Next
        }
        cur = cur.Next
    }
    if l1 != nil {
        cur.Next = l1
    }
    if l2 != nil {
        cur.Next = l2
    }
    return preHead.Next
}

  • 时间复杂度：O(N)

  • 空间复杂度：O(1)

2、合并 k 个有序链表

最小堆：利用 go 语言的提供的 heap 堆，自己实现 heap.Interface 接口定义的五个方法，从而实现一个最小堆。将所有的链表的头节点放入堆中，然后取出堆顶节点放入结果链表中，判断该节点的next节点是否为 nil，如果是 nil 表示该节点所在链表已遍历完毕；如果不是 nil，则将该节点的next节点放入堆中。继续遍历，直到堆的长度为0，表示所有的链表都已遍历完毕。

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
func mergeKLists(lists []*ListNode) *ListNode {
    h := &minHeap{}
    for _, list := range lists {
        if list != nil {
            heap.Push(h, list)
        }
    }

    preHead := &ListNode{}
    cur := preHead
    for h.Len() > 0 {
        tmp := heap.Pop(h).(*ListNode)	// 从堆中找出最小的节点，插入到结果链表
        cur.Next = tmp
        if tmp.Next != nil {
            heap.Push(h, tmp.Next)		// 将最小节点的next节点放入堆中
        }
        cur = cur.Next
    }
    return preHead.Next
}

type minHeap []*ListNode

func (h minHeap) Len() int           { return len(h) }
func (h minHeap) Less(i, j int) bool { return h[i].Val < h[j].Val }
func (h minHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x interface{}) {
	*h = append(*h, x.(*ListNode))
}
func (h *minHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

假设链表数量是 k，链表长度是 N：

  • 时间复杂度：O(Nlogk)
  • 空间复杂度：O(k)
3、寻找/删除单链表的倒数第 k 个节点

双指针：first 指针先从链表头节点移动 k 步，然后 second 与 first 指针同时移动，当 first 指针指向链表尾部的时候，second 指针指向的就是链表的倒数第 k 个节点。

寻找和删除倒数第 k 个节点都是相同的思路，下面的代码展示的是删除，不同点在于用了一个 pre 指针指向 second 节点，用于删除要删除的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    preHead := &ListNode{
        Next: head,
    }
    first := head
    for n > 0 {		// 第一个节点先移动n步
        first = first.Next
        n--
    }

    pre, second := preHead, head
    for first != nil {		// 两个节点一起移动，直到first到达链表尾部
        pre, second = second, second.Next
        first = first.Next
    }
    pre.Next = second.Next
    return preHead.Next
}
  • 时间复杂度：O(N)
  • 空间复杂度：O(1)
4、寻找单链表的中点

快慢指针：slow 每次移动一步，fast 每次移动两步，当 fast 或者 fast.Next 为空时，slow指针移到了链表的中间节点。

1
2
3
4
5
6
7
8
9
10
11
func middleNode(head *ListNode) *ListNode {
    if head.Next == nil {
        return head
    }
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    return slow
}
  • 时间复杂度：O(N)
  • 空间复杂度：O(1)
5、判断单链表是否包含环并找出环起点

快慢指针：首先，快慢指针都从表头开始移动，慢指针每次移动一步，快指针每次移动两步，直到两者相遇；然后将快指针指向链表表头，快慢指针再以相同的速度向后移动，当两者再次相遇时，相遇的位置就是环的起点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func detectCycle(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            slow := head	// fast指向头节点，然后fast与slow以相同的速度相后移动
            for slow != fast {	// 当slow与fast再次相遇时，代表找到了环的头节点
                slow = slow.Next
                fast = fast.Next
            }
            return fast
        }
    }
    return nil	// 如果链表没有环，会在fast到达结尾时跳出循环，因此在这里返回nil即可
}
  • 时间复杂度：O(N)
  • 空间复杂度：O(1)
6、判断两个单链表是否相交并找出交点

双指针：首先用两个指针分别从两个链表的头节点逐步移动，当指针指向链表结尾时，将该指针指向另一个链表的头节点，直到这两个指针相等时，就代表找到了两个链表相交的节点。

如果两个链表没有相交，最后两个指针都会移到链表结尾，都是 nil，最后返回 nil。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    curA, curB := headA, headB
    for curA != curB {
        if curA == nil {
            curA = headB
            
        } else {
            curA = curA.Next
        }
        if curB == nil {
            curB = headA
        } else {
            curB = curB.Next
        }
    }
    return curA
}
  • 时间复杂度：O(N)
  • 空间复杂度：O(1)