面试必备 LeetCode 链表算法题汇总，全程干货！

Wu_Candy

发布于 2022-07-04 21:19:57

5630

文章被收录于专栏：无量测试之道无量测试之道

引言：

搜集题目的难度是在简单级别和中级级别，也是面试常考的题目。题目的题解，使用的开发语言是Swift。

因为题目的描述很长，以及有各种案例提示，为了不占篇幅，所以没有展示出来，大家可以直接通过题号查询去查看题目的描述。

文章的写作顺序是：

1. 展示题号和以及题目的链接

2. 核心思想的讲述

3. 代码实现。

最后本文提供的代码都是在LeetCode上提交通过的。

1. Linked List Questions（链表相关问题）

1.LeetCode_141: 链表是否有环 2.LeetCode_160: 相交链表 3.LeetCode_206: 链表反转 4.LeetCode_ 21: 合并两个有序链表 5.剑指offer_ 22: 链表中倒数第k个节点 6.剑指Offer_ 06: 从尾到头打印链表 7.LeetCode_ 19: 删除链表的倒数第 N 个结点 8.LeetCode_237: 删除链表中的节点 9.LeetCode_ 83: 删除排序链表中的重复元素 10.LeetCode_ 82: 删除排序链表中的所有重复元素 II 11.LeetCode_203: 删除链表里某个值的所有节点 12.LeetCode_ 86: 分隔链表 13.LeetCode_328: 奇偶链表

1. 链表是否有环

1.1 核心思想讲解

这个思想使用的是快慢指针。 类比：就比如学校操场，A、B两人跑围着操场跑步，A跑的慢，B跑的快，他们从开始起跑后，随着时间的推移，最终他们会在操场的某个地点相遇。如果A、B在一个高速公路上跑，一个慢一个快，他们始终都没有机会相遇。快慢指针就是使用上述的原理，slow指针一次走一步，quick指针一次走两步。通过这样的方式遍历整个链表。如果没相遇就说明没有环，就像高速公路。如果彼此相遇了，说明有环，就像学校操场上的环形跑道。

1.2 代码实现


func hasCycle(_ head: ListNode?) -> Bool {
    if head == nil || head?.next == nil { return false }
    var slow = head
    var fast = head?.next

    while fast != nil && fast?.next != nil {
        if slow === fast { return true }
        slow = slow?.next
        fast = fast?.next?.next
    }

    return false
}

2. 链表相交

2.1 核心思想讲解

你变成我，我变成你，我们便相遇了。那么为什么能相遇呢？设长链表 A 长度为 LA，短链表长度 LB；由于速度相同，则在长链表 A 走完 LA 长度时，短链表 B 已经反过头在 A 上走了 LA-LB 的长度，剩余要走的长度为 LA-(LA-LB) = LB；之后长链表 A 要反过头在 B上走，剩余要走的长度也是 LB；也就是说目前两个链表“对齐”了。因此，接下来遇到的第一个相同节点便是两个链表的交点。那如果两个链表不存在交点呢？答：这样的话第 4 步就会一直执行到两个链表的末尾，la,lb 都为 null,也会跳出循环，返回null。

2.2 代码实现

func getIntersectionNode(_ headA: ListNode?, _ headB: ListNode?) -> ListNode? {
        var currentA = headA
        var currentB = headB
        //  !== 用的是对像不等于 不是 !=
        while currentA !== currentB {
        currentA = (currentA != nil) ? currentA?.next : headB
        currentB = (currentB != nil) ? currentB?.next : headA
      }
        return currentA
    }

3.链表反转

3.1 解题方法讲解

设置三个节点pre、cur、next （1）每次查看cur节点是否为NULL，如果是，则结束循环，获得结果（2）如果cur节点不是为NULL，则先设置临时变量next为cur的下一个节点（3）让cur的下一个节点变成指向pre，而后pre移动cur，cur移动到next （4）重复（1）（2）（3）（5）返回pre）

3.2 代码实现

func reverseList(_ head: ListNode?) -> ListNode? {
    var pre: ListNode?
    var cur = head
    var next = head?.next
    while cur != nil {
        next = cur?.next
        cur?.next = pre // 反转, 指向pre
        pre = cur
        cur = next
    }
    return pre
}

4. 合并两个有序链表

4.1 算法核心思想

因为一开始不好判断l1和l2谁是空节点，所以创建 dummy这个空节点; 通过两个链表的节点 val 大小对比，更新空链表指针 cur 值每次更新 cur 值后，同时更新两个有序链表指针，保存链表指针 cur 到最新位置最后 return 到 dummy.next，即头节点可得整个链表

4.2 代码实现

func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
    if l1 == nil { return l2 }
    if l2 == nil { return l1 }
    // 创建一个空节点，并让cur指针指向它，为最后返回结果提供了便利性，是一个很好的技巧
    var dummy = ListNode()
    var cur: ListNode? = dummy
    var headA = l1
    var headB = l2

    while headA != nil && headB != nil {
        if headA!.val < headB!.val {
            cur?.next = headA
            headA = headA?.next
        } else {
            cur?.next = headB
            headB = headB?.next
        }
        cur = cur?.next
    }

    if headA == nil {
        cur?.next = headB
    }

    if headB == nil {
        cur?.next = headA
    }
    return dummy.next
}

5. 链表中倒数第k个节点

5.1 核心思想

双指针 l r r指针先走k-1步，这样l指针和r指针之间就相差k-1。这个时候l和r一起往后遍历，当r走到链表末尾的时候，l指针刚好是倒数第k个节点

5.2 代码实现

func getKthFromEnd(_ head: ListNode?, _ k: Int) -> ListNode? {
    if head == nil || k == 0 { return head }
    var count = k
    var l: ListNode? = head
    var r: ListNode? = head
    while count > 1 {
        guard let node = r?.next else { return nil }
        count -= 1
        r = node
    }
    while r?.next != nil {
        l = l?.next
        r = r?.next
    }
    
    return l
}

6. 倒序打印链表

6.1 核心思想

既然倒序，那就用递归

6.2 代码实现


var nums = [Int]()
func reversePrint(_ head: ListNode?) -> [Int] {
    if head == nil { return nums }
    reverse(head)
    nums.append(head!.val)
    return nums
}

func reverse(_ head: ListNode?) {
    guard let next = head?.next else { return }
    reverse(head?.next)
    nums.append(next.val)
}

或者这样：

var nums = [Int]()
func reversePrint(_ head: ListNode?) -> [Int] {
    guard let head = head else {
        return []
    }
    reversePrint(head.next)
    nums.append(head.val)
    return nums
}

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

7.1 核心思想

这个题目和第5题的思想是一样的。但是有一个很特殊的情况：假设链表的长度是N，删除倒数第N个节点就是头结点了。为了处理这个特殊的情况，我们可以从第4题中得到灵感，就是创建一个虚拟的空节点dummy，并让dummy.next = head即可。

7.2 代码实现

func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
    if head == nil || n == 0 { return nil }
    var count = n
    var dummy = ListNode(0,head)
    var first: ListNode? = dummy
    var second: ListNode? = dummy
    
    while count > 0 {
        guard let node = second?.next else { return nil }
        second = node
        count -= 1
    }
    
    while second?.next != nil  {
        second = second?.next
        first = first?.next
    }
    first?.next = first?.next?.next
    return dummy.next
}

8. 删除链表中的节点

8.1 核心思想

思路分析如果我们要在链表中删除一个节点，一般的操作是：修改要删除节点的上一个节点的指针将该指针指向要删除节点的下一个节点例如，在链表 [4, 5, 1, 9] 中，当我们要删除节点5 时，我们会修改节点 5 上一个节点 4 的指针，让它指向节点 5 的下一个节点，即节点 1. 但这道题只告诉我们要删除的节点，我们并不知道该节点的上一个节点是什么，这时候又该如何是好呢？既然我们要删除一个节点时需要知道它的上一个节点，如果我们无法得知上一个节点，我们就找一个可以知道上一个节点的节点，把它变成要删除的节点，然后删除它。这样听起来好像有些拗口？没事，直接看一个例子！还是 [4, 5, 1, 9] 链表，还是删除节点 5。首先，我们把节点 5 下一个节点的值赋给它，节点变成了[4, 1, 1, 9] 然后删除第三个节点1即可

8.2 代码实现

func deleteNode(_ node: ListNode?) {
    guard let node = node else { return }
    var nextNode = node.next
    node.val = nextNode!.val
    node.next = nextNode!.next
}

9. 删除排序链表中的重复元素

9.1 核心思想

指定 cur 指针指向头部 head 当 cur 和 cur.next 的存在为循环结束条件，当二者有一个不存在时说明链表没有去重复的必要了当 cur.val 和 cur.next.val 相等时说明需要去重，则将 cur 的下一个指针指向下一个的下一个，这样就能达到去重复的效果如果不相等则 cur 移动到下一个位置继续循环

解法二：

还有一种解法：灵感来源于2数之和的那道算法题，使用map的去重的思想。

9.2 代码实现

 func deleteDuplicates(_ head: ListNode?) -> ListNode? {
        if head == nil {  return nil }
        var cur = head
        while cur != nil && cur?.next != nil {
            if cur!.val == cur!.next!.val {
                cur?.next = cur?.next?.next
            } else {
                cur = cur?.next
            }
        }
        return head
    }


    func removeDuplicateNodes(_ head: ListNode?) -> ListNode? {
        if head == nil { return nil }
        var map:[Int: ListNode] = [:]
        var p = head
        map[p!.val] = p!
        while p?.next != nil {
            if map[p!.next!.val] != nil {
                p!.next = p!.next!.next
            } else {
                map[p!.next!.val] = p!.next!
                p = p?.next
            }
        }
        return head
    }

10. 删除排序链表中的所有重复元素 II

10.1 核心思想

由于给定的链表是排好序的，因此重复的元素在链表中出现的位置是连续的，因此我们只需要对链表进行一次遍历，就可以删除重复的元素。由于链表的头节点可能会被删除，因此我们需要额外使用一个哑节点（dummy node）指向链表的头节点。具体地，我们从指针 cur 指向链表的哑节点，随后开始对链表进行遍历。如果当前 cur.next 与 cur.next.next 对应的元素相同，那么我们就需要将 cur.next 以及所有后面拥有相同元素值的链表节点全部删除。我们记下这个元素值 x，随后不断将 cur.next 从链表中移除，直到 cur.next 为空节点或者其元素值不等于 x 为止。此时，我们将链表中所有元素值为 x 的节点全部删除。如果当前 cur.next 与 cur.next.next 对应的元素不相同，那么说明链表中只有一个元素值为 cur.next 的节点，那么我们就可以将 cur 指向 cur.next。当遍历完整个链表之后，我们返回链表的的哑节点的下一个节点 dummy.next 即可。

10.2 代码实现

func deleteDuplicates(_ head: ListNode?) -> ListNode? {
        if head == nil { return nil }
        var dummy = ListNode(0,head)
        var cur: ListNode? = dummy
        while cur?.next != nil && cur?.next?.next != nil {
            if cur!.next!.val == cur!.next!.next!.val {
                let x = cur!.next!.val
                // 二次 while 删掉重复的节点
                while cur?.next != nil && cur!.next!.val == x {
                    cur?.next = cur?.next?.next
                }
            } else {
               cur = cur?.next
            }
        }
        return dummy.next
    }

11. 删掉链表里某个值的所有节点

11.1 核心思想

因为担心头节点也是删除的节点，所以开始的时候加一个dummy虚拟节点。后续的就是删除操作了。特别是cur?.next = cur?.next?.next // 执行删除 这句话，就是一直删，直到下个节点值不等于val，才让cur = cur?.next

11.2 代码实现

 func removeElements(_ head: ListNode?, _ val: Int) -> ListNode? {
        if head == nil { return head }
        var dummy = ListNode(0, head)
        var cur: ListNode? = dummy
        while cur?.next != nil {
            if cur!.next!.val == val {
                cur?.next = cur?.next?.next // 执行删除
            }else {
                cur = cur?.next
            }
        }
        return dummy.next
    }

12. 分割链表

12.1 核心思想

2 个新的链表来保存，到最后再把两个2链表链接起来即可

12.2 代码实现

func partition(_ head: ListNode?, _ x: Int) -> ListNode? {
    if head == nil { return nil }
    var node = head
    var lHead = ListNode(0), lTrail = lHead
    var rHead = ListNode(0), rTrail = rHead
    while node != nil {
        if node!.val < x {
            lTrail.next = node
            lTrail = lTrail.next! //lTrail = curHead!
        }else {
            rTrail.next = node
            rTrail = rTrail.next! //  rTrail = curHead!
        }
        node = node?.next
    }
    rTrail.next = nil
    lTrail.next = rHead.next
    return lHead.next
}

13. 奇偶链表

13.1 核心思想

和12题的的解法是一样的，就是更改了判断条件而已

13.2 代码实现

 func oddEvenList(_ head: ListNode?) -> ListNode? {
        if head == nil { return nil }
        var node = head
        var lHead = ListNode(0), lTrail = lHead
        var rHead = ListNode(0), rTrail = rHead
        var flag = false
        while node != nil {
            if !flag {
                lTrail.next = node
                lTrail = lTrail.next!
            }else {
                rTrail.next = node
                rTrail = rTrail.next! //  rTrail = curHead!
            }
            flag.toggle()
            node = node?.next
        }
        rTrail.next = nil
        lTrail.next = rHead.next
        return lHead.next
    }

end

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-07-30，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自无量测试之道微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度