Table of Contents
Remove Nth Node From End of List
Naive Golang solution
Logic
- Always start from head; slow, fast := head, head
- Traverse n+1 position from beginning of list, move fast pointer to n+1 position
- edge case : if n == len(of list), then we have to delete head, return head.Next
- Start traversing both slow and fast, until fast reaches last node
- i.e. fast.Next == nil
func removeNthFromEnd(head *ListNode, n int) *ListNode {
slow := head
fast := head
// find the (n+1) th node from beginning
for i := 0; i < n; i++ {
if fast != nil {
fast = fast.Next
}
}
// edge case : if n == len(of list),
// then we have to delete head, return head.Next
// this means we have to delete head
// after traversing n positions from end
if fast == nil {
return head.Next
}
// Start traversing both slow and fast, until fast reaches last node
for fast.Next != nil {
slow = slow.Next
fast = fast.Next
}
slow.Next = slow.Next.Next
return head
}Optimised simple Code
func removeNthFromEnd(head *ListNode, n int) *ListNode {
// Use a dummy node to simplify edge cases
dummy := &ListNode{Next: head}
slow, fast := dummy, dummy
// Move fast pointer n+1 steps ahead to maintain a gap of n
for i := 0; i <= n; i++ {
if fast == nil {
return head // n is larger than the list size
}
fast = fast.Next
}
// Move both slow and fast pointers until fast reaches the end
for fast != nil {
slow = slow.Next
fast = fast.Next
}
// Remove the nth node from end
slow.Next = slow.Next.Next
// Return the updated list, dummy.Next skips the dummy node
return dummy.Next
}
Minor improvement
Explanation of Changes
- Store the node to be deleted (
toDelete):- Before modifying the
slow.Nextpointer, store a reference to the node that is about to be deleted.
- Before modifying the
- Dereference the node:
- Set
toDelete.Nexttonilto disconnect it from the list. - Set
toDeletetonilto ensure it is not referenced anywhere in the code.
- Set
Why Dereferencing Helps
Dereferencing the node ensures it is no longer part of the linked list and not reachable from any other part of the program. This makes it eligible for garbage collection more promptly.
While Go’s garbage collector generally handles memory management well, dereferencing is a good practice when dealing with large data structures or critical applications where memory needs to be freed as soon as possible.
// Remove the nth node from end
toDelete := slow.Next
slow.Next = slow.Next.Next
// Dereference the node to be deleted
toDelete.Next = nil
toDelete = nilKey Changes and Why ?
- Dummy Node:
- Simplifies edge cases like removing the first node.
- Always ensures
slow.Nextpoints to the node to be removed.
- Fast Pointer Initialization:
- Moves
fastn+1 steps ahead to maintain a clear n-node gap withslow.
- Moves
- Simplified Logic for Node Removal:
- Avoids redundant checks for
previousand directly usesslow.
- Avoids redundant checks for
- Edge Case for Invalid
n:- If
n > length of the list, the code exits early.
- If
Example Test Cases
func main() {
// Test case 1: Remove the 2nd node from the end
head := &ListNode{}
for i := 1; i <= 5; i++ {
AddNode(&head, i)
}
fmt.Println("Original list:")
printList(head)
head = removeNthFromEnd(head, 2)
fmt.Println("After removing 2nd node from end:")
printList(head)
// Test case 2: Remove the 1st node (head node)
head = &ListNode{}
for i := 1; i <= 5; i++ {
AddNode(&head, i)
}
head = removeNthFromEnd(head, 5)
fmt.Println("After removing head:")
printList(head)
// Test case 3: Single node list, remove the only node
head = &ListNode{Val: 1}
head = removeNthFromEnd(head, 1)
fmt.Println("After removing the only node:")
printList(head)
}
Visit https: https://codeandalgo.com for more such contents
Leave a Reply