Algorithem_TwoPointersOfLinked List#
876. 鏈表的中間節點#
給定一個單鏈表的頭節點，返回鏈表的中間節點。
如果有兩個中間節點，返回第二個中間節點。
範例 1:
Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: 鏈表的中間節點是節點 3。
範例 2:
Input: head = [1,2,3,4,5,6]
Output: [4,5,6]
Explanation: 由於鏈表有兩個中間節點，值為 3 和 4，因此返回第二個。
解法#
單看例子，感覺是獲取數組中間位置到末尾，這個跟 TwoPointer 有什麼關係呢？看到給的代碼，明白了，不是數組，給出的是一個 ListNode
定義的代碼如下:
/**
* Definition for singly-linked list.
* public class ListNode {
* public var val: Int
* public var next: ListNode?
* public init() { self.val = 0; self.next = nil; }
* public init(_ val: Int) { self.val = val; self.next = nil; }
* public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
* }
*/
class Solution {
func middleNode(_ head: ListNode?) -> ListNode? {
}
}
這裡一開始沒理解給出的 ListNode 和上面範例中的 head 是怎麼對應起來的。
看了好久明白了，
鏈表
1 -> 2 -> 3 -> 4 -> 5
val 1
next 2
val 2
next 3
val 3
next 4
val 4
next 5
val 5
next nil
理解了 listNode 之後，那如何獲取中間的 ListNode 呢？
定義兩個變量，s 和 f，每次循環 s 指向下一個元素，而 f 指向下下個元素，這樣最後 f 結束時，s 指向的就是中間。
/*
最開始
f
1 -> 2 -> 3 -> 4 -> 5
s
第一次循環
f
1 -> 2 -> 3 -> 4 -> 5
s
第二次循環
f
1 -> 2 -> 3 -> 4 -> 5
s
第三次循環
當 f 的 next 為空時結束，此時 s 指向的是中間
f = fast pointer
s = slow pointer
*/
最終代碼如下：
/**
* Definition for singly-linked list.
* public class ListNode {
* public var val: Int
* public var next: ListNode?
* public init() { self.val = 0; self.next = nil; }
* public init(_ val: Int) { self.val = val; self.next = nil; }
* public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
* }
*/
class Solution {
func middleNode(_ head: ListNode?) -> ListNode? {
var slow = head
var fast = head
while (fast != nil) && (fast?.next != nil) {
slow = slow?.next
fast = fast?.next?.next
}
return slow
}
}
19. 刪除鏈表的倒數第 N 個節點#
給定一個鏈表的頭節點，刪除鏈表的倒數第 n 個節點並返回其頭節點。
範例 1:
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
範例 2:
Input: head = [1], n = 1
Output: []
範例 3:
Input: head = [1,2], n = 1
Output: [1]
解法#
這個地方，需要注意的是 nth node from the end of the list，是從末尾數第幾個。
想法是首先獲取整個長度，然後整個的長度減去 (n - 1)，就是正著數的第幾個，從 1 開始的，然後賦值，從頭開始賦值，如果剛好到這個時，則跳過。
但是使用 TwoPoint 的算法是，定義 slow 和 fast，然後先讓 fast 向前走 n 步，再 slow 和 fast 一起向前走，這樣當 fast 走到尾部時，slow 剛好要移除的位置，然後跳過這個元素賦值。
代碼如下：
/**
* Definition for singly-linked list.
* public class ListNode {
* public var val: Int
* public var next: ListNode?
* public init() { self.val = 0; self.next = nil; }
* public init(_ val: Int) { self.val = val; self.next = nil; }
* public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
* }
*/
class Solution {
func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
let node = ListNode(0, head)
var slow: ListNode? = node
var fast: ListNode? = node
var m = n
while (m > 0) {
fast = fast?.next
m -= 1
}
while fast?.next != nil {
slow = slow?.next
fast = fast?.next
}
slow?.next = slow?.next?.next
return node.next
}
}