アルゴリズム_リンクリストの 2 つのポインタ#
876. リンクリストの中央#
単方向リンクリストのヘッドが与えられた場合、リンクリストの中央ノードを返します。
もし中央のノードが 2 つある場合は、2 番目の中央ノードを返します。
例 1:
入力: head = [1,2,3,4,5]
出力: [3,4,5]
説明: リストの中央ノードはノード3です。
例 2:
入力: head = [1,2,3,4,5,6]
出力: [4,5,6]
説明: リストには値が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 と上記の例の 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:
入力: head = [1,2,3,4,5], n = 2
出力: [1,2,3,5]
例 2:
入力: head = [1], n = 1
出力: []
例 3:
入力: head = [1,2], n = 1
出力: [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
}
}