title: Algorithm_TwoPointersOfLinkedList
tags:
- Technology
- Algorithm
date: 2022-04-18 10:15#
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#
Based on the examples, it seems like we need to find the middle position to the end of an 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 defined 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 and the head in the Example corresponded.
After looking at it for a while, I understood.
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
Once I understood 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, it's important to note that "nth node from the end of the list" means counting from the end, starting from 1. The idea is to first get the total length, 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. First, we let fast move forward n steps, then both slow and fast move forward together. This way, when fast reaches the end, slow is exactly at the position to be removed. We then skip this element and assign the next value.
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
}
}