Algorithm_TwoPointersOfLinkedList#
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.
Solution#
At first glance, it seems like we need to find the middle position to the end of the array. What does this have to do with TwoPointers? After looking at the given code, it becomes clear that it's not an array, but a ListNode.
The definition of the code is as follows:
/**
* 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? {
}
}
At first, I didn't understand how the given ListNode corresponds to the head in the Example above.
After looking at it for a while, I understood it.
Linked List
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
After understanding the ListNode, how do we get the middle ListNode?
We define two variables, s and f. In each iteration, s points to the next element, while f points to the next next element. This way, when f finishes, s points to the middle.
/*
Initial state
f
1 -> 2 -> 3 -> 4 -> 5
s
First iteration
f
1 -> 2 -> 3 -> 4 -> 5
s
Second iteration
f
1 -> 2 -> 3 -> 4 -> 5
s
Third iteration
The loop ends when f's next is nil, and at this point, s points to the middle.
f = fast pointer
s = slow pointer
*/
The final code is as follows:
/**
* 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]
Solution#
In this case, we need to pay attention to "nth node from the end of the list," which means counting from the end. The idea is to first get the total length and then subtract (n - 1) from the total length to get the position from the front, starting from 1. Then, we assign values starting from the head, and if we reach that position, we skip it.
However, using the TwoPointers algorithm, we define slow and fast, and first let fast move forward n steps, then both slow and fast move forward together. This way, when fast reaches the end, slow is at the position to be removed, and we skip this element and assign values.
The code is as follows:
/**
* 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
}
}