Remove Nth Node From End of List

 

1. Clarify the problem: Before diving into solving the problem, let's clarify the requirements:

  • We are given a linked list of nodes.
  • We need to remove the nth node from the end of the list and return the modified list.

2. Analyze the problem: To solve this problem, we can use a two-pointer approach.

  • We can maintain two pointers, fast and slow, that are initially pointing to the head of the linked list.
  • We move the fast pointer n steps ahead.
  • Then, we move both pointers simultaneously until the fast pointer reaches the end of the list.
  • At this point, the slow pointer will be pointing to the node that needs to be removed.
  • To remove the node, we update the next pointer of the previous node to point to the next node of the slow pointer.

3. Design an algorithm: Here is the algorithm to solve the problem:

  1. Initialize a dummy node and set its next pointer to the head of the linked list. This helps handle the case where the head itself needs to be removed.
  2. Initialize two pointers, fast and slow, to point to the dummy node.
  3. Move the fast pointer n steps ahead.
  4. While the fast pointer is not None:
    • Move both the fast and slow pointers one step at a time.
  5. Update the next pointer of the slow pointer to skip the node that needs to be removed.
  6. Return the next pointer of the dummy node as the modified linked list.

4. Explain your approach: The approach involves using two pointers, fast and slow, to traverse the linked list. We move the fast pointer n steps ahead of the slow pointer. Then, we move both pointers simultaneously until the fast pointer reaches the end of the list. At this point, the slow pointer will be pointing to the node that needs to be removed. We update the next pointer of the previous node to point to the next node of the slow pointer, effectively removing the desired node.

5. Write clean and readable code:

python
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def removeNthFromEnd(head, n):
    dummy = ListNode(0)
    dummy.next = head
    fast = slow = dummy

    for _ in range(n):
        fast = fast.next

    while fast.next:
        fast = fast.next
        slow = slow.next

    slow.next = slow.next.next

    return dummy.next

6. Test your code: Let's test the code with some test cases:

python
# Test case 1
head1 = ListNode(1)
head1.next = ListNode(2)
head1.next.next = ListNode(3)
head1.next.next.next = ListNode(4)
head1.next.next.next.next = ListNode(5)
n1 = 2
result1 = removeNthFromEnd(head1, n1)
while result1:
    print(result1.val)
    result1 = result1.next
# Output: 1 -> 2 -> 3 -> 5

# Test case 2
head2 = ListNode(1)
n2 = 1
result2 = removeNthFromEnd(head2, n2)
if result2:
    print(result2.val)
else:
    print("Empty list")
# Output: Empty list

7. Optimize if necessary: The code uses a two-pointer approach, which is an efficient solution with a time complexity of O(L), where L is the length of the linked list. There is no obvious optimization available for this problem.

8. Handle error cases: The code assumes that the input linked list is valid and satisfies the problem constraints. If the linked list is empty or the value of n is invalid (e.g., negative or greater than the length of the linked list), the behavior of the code is undefined.

9. Discuss complexity analysis:

  • The time complexity of this solution is O(L), where L is the length of the linked list. We traverse the linked list twice at most.
  • The space complexity is O(1) since we only use a constant amount of additional space to store the pointers.
  • The solution has an optimal time and space complexity given the problem requirements.
Next Post Previous Post