アルゴリズム_リンクリストの 2 つのポインタ#
876. リンクリストの中央#
単方向リンクリストのヘッドが与えられた場合、リンクリストの中央のノードを返します。
もし中央のノードが 2 つある場合は、2 番目の中央のノードを返します。
例 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の2つの中央のノードがあるため、2番目のノードを返します。
解法#
例を見る限り、配列の中央から末尾までを取得するように見えますが、これは 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 と Example の 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 を取得するのでしょうか？
2 つの変数、s と f を定義し、各ループで s は次の要素を指し、f は次の次の要素を指すようにします。最終的に f が終了するとき、s が指すのは中央の要素です。
/*
最初
f
1 -> 2 -> 3 -> 4 -> 5
s
1回目のループ
f
1 -> 2 -> 3 -> 4 -> 5
s
2回目のループ
f
1 -> 2 -> 3 -> 4 -> 5
s
3回目のループ
f の next が nil の場合、終了し、この時点で s は中央を指しています。
f = 高速ポインタ
s = 遅いポインタ
*/
最終的なコードは以下の通りです：
/**
* 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]
解法#
この部分では、リンクリストの末尾から n 番目のノードを削除する必要があることに注意してください。n は末尾から数えたものです。
アイデアはまずリストの全体の長さを取得し、その長さから (n - 1) を引いたものが 1 から数えた正しい位置です。その位置から順に値を割り当て、ヘッドから割り当てを開始します。ちょうどその位置に到達した場合は、スキップします。
しかし、TwoPointer のアルゴリズムを使用する場合は、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
}
}