Algorithem_TwoPointersOfLinked List#
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 が与えられていることがわかりました。
定義されたコードは以下の通りです:
/**
* 単方向リンクリストの定義。
* 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
最初のループ
f
1 -> 2 -> 3 -> 4 -> 5
s
2回目のループ
f
1 -> 2 -> 3 -> 4 -> 5
s
3回目のループ
fのnextがnilのとき終了し、この時sが指しているのが中央です。
f = ファストポインタ
s = スローポインタ
*/
最終的なコードは以下の通りです：
/**
* 単方向リンクリストの定義。
* 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]
解法#
ここで注意が必要なのは、nth node from the end of the list は末尾から数えた第 n 番目のノードであるということです。
考え方は、まず全体の長さを取得し、その長さから (n - 1) を引くことで、正方向から数えた第 n 番目のノードを求めます。1 から始まる数え方です。そして、頭から順にノードを数えます。ちょうどその位置に来たら、スキップします。
しかし、TwoPoint のアルゴリズムを使用する場合、slow と fast を定義し、最初に fast を n ステップ前に進め、その後 slow と fast を一緒に前に進めます。こうすることで、fast が末尾に到達したとき、slow がちょうど削除すべき位置にいます。その要素をスキップして値を設定します。
コードは以下の通りです：
/**
* 単方向リンクリストの定義。
* 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
}
}