leetcode19.Remove Nth Node From End of List

Problem Description

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Approach

To remove the nth node from the end of a linked list, we can use the two-pointer technique. We initialize two pointers, fast and slow, both initially pointing to a dummy node.

1. Initialize a dummy node dummyHead and set its next pointer to the head of the linked list. This dummy node helps us handle the case where the head itself needs to be removed.
2. Move the fast pointer n steps ahead in the linked list. This positions the fast pointer n+1 nodes ahead of the slow pointer.
3. Move both the fast and slow pointers simultaneously until the fast pointer reaches the end of the linked list.
4. At this point, the slow pointer is pointing to the (n-1)-th node from the end of the linked list. We update the slow.next pointer to skip the nth node and connect it to the (n+1)-th node.
5. Finally, we return the dummyHead.next as the new head of the modified linked list.

Implementation with Comments

public ListNode removeNthFromEnd(ListNode head, int n) {
    // Initialize a dummy node and set its next pointer to the head of the linked list
    ListNode dummyHead = new ListNode(0);
    dummyHead.next = head;
    
    // Initialize fast and slow pointers
    ListNode fast = dummyHead; // fast is n steps ahead of slow
    ListNode slow = dummyHead;

    // Move the fast pointer n steps ahead
    while (n-- > 0 && fast != null) {
        fast = fast.next;
    }
    
    // Move both the fast and slow pointers simultaneously until the fast pointer reaches the end of the linked list
    fast = fast.next; // to position fast pointer n+1 nodes ahead of slow pointer
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }

    // Update the slow.next pointer to skip the nth node and connect it to the (n+1)-th node
    slow.next = slow.next.next;

    // Return the dummyHead.next as the new head of the modified linked list
    return dummyHead.next;
}

Complexity Analysis

• Time complexity: O(L), where L is the length of the linked list. We need to traverse the entire linked list once.
• Space complexity: O(1), using only constant extra space.

The two-pointer technique allows us to remove the nth node from the end of the linked list in a single pass. The space complexity is constant because we are using only a fixed number of pointers.

This problem showcases a common operation on linked lists. By understanding the concept of the two-pointer technique and manipulating the pointers correctly, we can efficiently solve similar problems.

感谢您的来访，获取更多精彩文章请收藏本站。