---

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 }

小結

連結串列篇的初級演算法看看你都學會了嗎？連結串列的資料結構與陣列的區別在於，陣列在記憶體是連續的，而連結串列不需要連續。連結串列在插入和刪除上也比較靈活，但是在查詢時就比較麻煩，只能通過頭節點一個個向後遍歷查詢。在很多連結串列的處理上，大多數都可以使用遞迴的方式。

連結串列：棧、遞迴、快慢指標、集合、雙指標