当前位置:网站首页>面试必备 LeetCode 链表算法题汇总,全程干货!

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

2022-07-04 21:58:00 Wu_Candy

引言:

搜集题目的难度是在简单级别和中级级别,也是面试常考的题目。题目的题解,使用的开发语言是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 解题方法讲解

设置三个节点precurnext (1)每次查看cur节点是否为NULL,如果是,则结束循环,获得结果 (2)如果cur节点不是为NULL,则先设置临时变量nextcur的下一个节点 (3)让cur的下一个节点变成指向pre,而后pre移动curcur移动到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

原网站

版权声明
本文为[Wu_Candy]所创,转载请带上原文链接,感谢
https://cloud.tencent.com/developer/article/2040324