Algorithem_TwoPointersOfLinked List#
876. Middle of the Linked List#
Given the head of a singly linked list, return the middle node of the linked list.
If there are two middle nodes, return the second middle node.
Example 1:
Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3.
Example 2:
Input: head = [1,2,3,4,5,6]
Output: [4,5,6]
Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.
解法#
单看例子，感觉是获取数组中间位置到末尾，这个跟 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 呢？
定义两个变量，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. Remove Nth Node From End of List#
Given the head of a linked list, remove the nth node from the end of the list and return its head.
Example 1:
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
Example 2:
Input: head = [1], n = 1
Output: []
Example 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
}
}