Algorithem_TwoPointersOfLinked List

2022-04-18

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:

1
2
3

Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3.

Example 2:

1
2
3

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:

1 2	Input: head = [1,2,3,4,5], n = 2 Output: [1,2,3,5]

Example 2:

1 2	Input: head = [1], n = 1 Output: []

Example 3:

1 2	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
    }
}