---

theme: juejin highlight: xcode

---

本文正在参加「金石计划 . 瓜分6万现金大奖」

前言：最近自己也开始系统的刷面试题了，算法是过不去的坎，希望自己能够坚持下去✊，同行的朋友们共勉。

题一：删除链表中的节点

有一个单链表的 head，我们想删除它其中的一个节点 node。

给你一个需要删除的节点 node 。你将 无法访问 第一个节点  head。

链表的所有值都是 唯一的，并且保证给定的节点 node 不是链表中的最后一个节点。

示例 1：

输入：head = [4,5,1,9], node = 5 输出：[4,1,9] 解释：指定链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9

解题思路：直接替换

此题考查了链表的结构， 我们在删除、添加元素时，只需要修改引用对象指针即可； - 删除：去除引用关系，让当前节点被下一个节点替代 - 添加：被某个位置的节点引用

由于这里传入被删除的该节点，所以使用下一个节点来替换被删除节点就可以了。

swift func deleteNode(_ node: ListNode?, _ head: ListNode?) { node?.val = node?.next?.val ?? 0 node?.next = node?.next?.next ?? nil let head = head }

题二：删除链表的倒数第N个节点

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

示例 1： 输入： head = [1,2,3,4,5], n = 2 输出： [1,2,3,5]

解题思路：递归、双循环、快慢指针

这题同样在考查我们对链表的理解。

链表是线性数据结构，我们单从头节点中无法知道链表的长度。 通过遍历整个链表，我们才可以知道链表的长度。而确定了链表的长度之后，再去找到要被删除的元素就简单了。

递归

```swift func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? { let pos = length(head, n) if pos == n { return head?.next } return head }

func length(_ node: ListNode?, _ n: Int) -> Int { if node?.next == nil { return 1 } /// 获取前面一个节点 let pos = length(node?.next, n) + 1 if pos == n+1 { print("(pos)") node?.next = node?.next?.next } return pos } ```

双循环

第一次：确定链表长度 第二次：定位到n的位置，完成替换

```swift func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? { let pos = length(head, n) if pos == n { return head?.next } return head }

func length(_ node: ListNode?, _ n: Int) -> Int { if node?.next == nil { return 1 } /// 获取前面一个节点 let pos = length(node?.next, n) + 1 if pos == n+1 { print("(pos)") node?.next = node?.next?.next } return pos } ```

快慢指针

fast、slow两个指针，fast先走n次，然后和slow一起移动。 slow和fast相距n， 当fast先走到链表底部，slow就是要删除的对象；

swift func removeNthFromEnd3(_ head: ListNode?, _ n: Int) -> ListNode? { var fast = head var slow = head var index = n /// jNode 移位 n while index > 0 { fast = fast?.next index-=1 let j = fast } if fast?.next == nil { return head?.next } /// 开始遍历 while fast?.next != nil { fast = fast?.next slow = slow?.next } slow?.next = slow?.next?.next return head }

题三：反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

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

解题思路：栈、递归、双指针

将单向链表翻转等于是改变链表方向；

栈操作

先进后出、后进先出。利用栈的特性，反转链表。 - 入栈：1 —> 2 —> 3 - 出栈：3 —> 2 —> 1

swift func reverseList(_ head: ListNode?) -> ListNode? { /// 全部入栈 var node = head var stack = Stack<ListNode>() while node != nil { if let node = node { stack.push(element: node) } node = node?.next } /// 第一个出栈的节点是新的表头 node = stack.pop() /// 新的表头 var newHead = node while !stack.isEmpty() { let tempNode = stack.pop() node?.next = tempNode node = tempNode } node?.next = nil return newHead }

双指针

双指针：newHead、node\ 每次循环，缓存node指针的下一个节点，这里比较关键。 然后

swift func reverseList(_ head: ListNode?) -> ListNode? { var node = head var newhead: ListNode? = nil while node != nil { let temp = node?.next node?.next = newhead newhead = node node = temp } return newhead }

题四：合并两个有序链表

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

示例 1：

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

解题思路：双指针

合并两个升序的链表其实和数组的思想类似。只是实现上有点区别。但是都可以使用双指针去实现。 两个指针分别指向两个链表的头部节点，比较两个节点的值大小，小的一方添加到链表中，并且把指针往后移。

swift func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? { var node1 = list1 var node2 = list2 var newHead = ListNode(0) var cur: ListNode? = newHead while node1 != nil && node2 != nil { let val1 = node1?.val ?? 0 let val2 = node2?.val ?? 0 if val1 <= val2 { cur?.next = node1 node1 = node1?.next } else { cur?.next = node2 node2 = node2?.next } cur = cur?.next } cur?.next = node1 == nil ? node2 : node1 let head = newHead.next return head }

题五：回文链表

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

示例 1：

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

解题思路：栈操作、递归、反转后半链表

关键点就是对比首尾的各个节点；如何获取尾部的节点呢？答案是：栈操作、递归、反转后半链表。

递归也相当于栈操作

栈操作

先进后出、后进先出。

swift func isPalindrome(_ head: ListNode?) -> Bool { var node = head var stack = Stack<Int>() var length = 0 while node != nil { if let node = node { stack.push(element: node.val) } node = node?.next length+=1 } node = head length/=2 while length > 0 { if node?.val != stack.pop() { return false } node = node?.next length-=1 } return true }

反转后半链表

先找到中间链表 使用快慢指针 fast、slow (原理：fast+2，slow+1，fast到达终点，slow此时应该在中间）

判断奇偶数，如果fast不为空，则说明链表长度为奇数，若fast为空，则说明为偶数，找到中点，反转后半部分链表

判断反转后的链表是否和前半部分链表相同，如果全部相同则说明是回文链表，反之，则不是。

swift func isPalindrome(_ head: ListNode?) -> Bool { var fast = head var slow = head while fast != nil, fast?.next != nil { fast = fast?.next?.next slow = slow?.next } /// 奇数就选下一个 if fast != nil { slow = slow?.next } var newNode = reverse(slow) var node = head while newNode != nil { if newNode?.val != node?.val { return false } newNode = newNode?.next node = node?.next } return true }

题六：环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：

输入： head = [3,2,0,-4], pos = 1 输出： true 解释： 链表中有一个环，其尾部连接到第二个节点。 示例 2：

输入： head = [1], pos = -1 输出： false 解释： 链表中没有环。

解题思路：集合法、快慢指针

集合法

如果不考虑内存问题，我们可以使用集合来缓存每次到访的节点。如果下一次命中缓存，则说明有环。

swift func hasCycle(_ head: ListNode?) -> Bool { var node = head?.next var set = Set<ListNode>() while node != nil { if set.contains(node!) { return true } else { set.insert(node!) } node = node?.next } return false }

快慢指针

判断链表中有没有环，可以通过快慢指针来处理， slow走一步，fast走两步，如果有环，当走到n次时，slow和fast相遇。 如果没有环，fast会先走到尾部，变为nil。 swift func hasCycle(_ head: ListNode?) -> Bool { var slow = head?.next var fast = head?.next?.next while fast != nil { if slow === fast { return true } slow = slow?.next fast = fast?.next?.next } return false }

小结

链表篇的初级算法看看你都学会了吗？链表的数据结构与数组的区别在于，数组在内存是连续的，而链表不需要连续。链表在插入和删除上也比较灵活，但是在查找时就比较麻烦，只能通过头节点一个个向后遍历查找。在很多链表的处理上，大多数都可以使用递归的方式。

链表：栈、递归、快慢指针、集合、双指针