教程

双指针技巧秒杀七道链表题目

题目

合并两个有序链表

力扣-21-合并两个有序链表

  • 只用两个指针指向两个链表，每次取值的时候移动，如果俩链表中至少有一个遍历完成则结束，把没遍历完成的链表直接放在新链表的后面
    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
    /**
     * Definition for singly-linked list.
     * type ListNode struct {
     *     Val int
     *     Next *ListNode
     * }
     */
    func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
        // 此处纯属优化
        if list1 == nil {
            return list2
        }
        if list2 == nil {
            return list1
        }

        head := &ListNode{}
        // 这里为啥要重新赋值一下，因为最终结果需要返回第一个节点
        node := head
        p1 := list1
        p2 := list2

        for p1 != nil && p2 != nil {
            if p1.Val < p2.Val {
                node.Next = p1
                p1 = p1.Next
            } else {
                node.Next = p2
                p2 = p2.Next
            }
            node = node.Next
        }
        // 为啥有下面这两行，是因为可能某一个遍历完成，而另外一个还没有，姐可以直接放在后面了
        if p1 != nil {
            node.Next = p1
        }
        if p2 != nil {
            node.Next = p2
        }

        // 这里为啥是next, 因为我们为了方便head是一个无效的节点
        return head.Next
    }

分隔链表

力扣-86-分隔链表

  • 使用两个链表分别保存小于和大于或等于的值，最后合并。需要注意俩个点：1. 目标链表每遍历一个节点就把指针往后移动，并断开前面的节点；2. 合并的时候只需要判断保存大值的连边是否为空，如果不为空直接放在小值连边后面，最后返回小值链表的头部（注意：我们为了操作方便，在定义链表的时候第一个节点是无效节点，所以表头节点是第二个节点）。
    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.
     * type ListNode struct {
     *     Val int
     *     Next *ListNode
     * }
     */
    func partition(head *ListNode, x int) *ListNode {
        p1 := &ListNode{}
        p1Head := p1
        p2 := &ListNode{}
        p2Head := p2

        for head != nil {
            if head.Val < x {
                p1.Next = head
                p1 = p1.Next
            } else {
                p2.Next = head
                p2 = p2.Next
            }

            // 断开已经处理完成的节点
            temp := head.Next
            head.Next = nil
            head = temp
        }

        // 大值链表不为空就直接放在后面
        if p2Head.Next != nil {
            p1.Next = p2Head.Next
        }

        return p1Head.Next
    }

反馈倒数第K个节点

力扣-2-返回倒数第K个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func kthToLast(head *ListNode, k int) int {
    p := head

    for i := 1; i <= k; i++ {
        head = head.Next
    }

    for head != nil {
        head = head.Next
        p = p.Next
    }

    return p.Val
}

返回中间接点

  • 其实就是利用快慢指针

力扣-876-链表中加结点

1
2
3
4
5
6
7
8
9
10
func middleNode(head *ListNode) *ListNode {
    fast, slow := head, head

    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
    }

    return slow
}

环形链表

力扣-141-环形链表

1
2
3
4
5
6
7
8
9
10
11
12
13
func hasCycle(head *ListNode) bool {
    fast, slow := head, head

    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            return true
        }
    }

    return false
}

环形链表II

环形链表II【基础算法精讲 07】_哔哩哔哩_bilibili
力扣-142-环形链表II

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
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
    slow, fast := head, head

    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next

        if fast == slow {
            for head != slow {
                head = head.Next
                slow = slow.Next
            }

            return slow
        }
    }

    return nil
}

相交链表

力扣-160-相交链表

双指针-暴力破解
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.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    for headA != nil {
        tempB := headB
        for tempB != nil {
            if tempB == headA {
                return tempB
            }
            tempB = tempB.Next
        }

        headA = headA.Next
    }

    return 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
    25
    26
    /**
     * 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 = headB
            } else {
                a = a.Next
            }

            if b == nil {
                b = headA
            } else {
                b = b.Next
            }
        }

        return a
    }