19. Remove Nth Node From End of List#

Difficulty: Medium

Link to Problem: To see the Remove Nth Node From End of List problem on LeetCode, click here!

Given the head of a linked list, remove the \(n^{th}\) node from the end of the list and return its head.

Constraints:

  • The number of nodes in the list is sz.

  • 1 <= sz <= 30

  • 0 <= Node.val <= 100

  • 1 <= n <= sz

Follow up: Could you do this in one pass?

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

def removeNthFromEnd(head, n):
    # Create a dummy node to handle the case of removing the head node.
    dummy = ListNode(0)
    dummy.next = head
    first = dummy
    second = dummy
    
    # Advance the first pointer by n+1 nodes.
    for _ in range(n + 1):
        first = first.next
    
    # Move both pointers simultaneously until first reaches the end.
    while first is not None:
        first = first.next
        second = second.next
    
    # Remove the nth node by updating the next pointer of the previous node.
    second.next = second.next.next
    
    return dummy.next  # Return the modified head of the linked list

Explanation:#

  1. We start by defining a ListNode class to represent individual nodes in a linked list. Each node has two attributes: val (the value of the node) and next (a reference to the next node in the list).

  2. The removeNthFromEnd function takes the head of a linked list (head) and the value n, which represents the position from the end of the list of the node to be removed. It returns the modified head of the linked list after the removal.

  3. We create a dummy node (dummy) at the beginning of the list. This dummy node simplifies the code by handling cases where the head of the list needs to be removed.

  4. We initialize two pointers, first and second, both initially pointing to the dummy node.

  5. To advance the first pointer by n+1 nodes, we use a for loop. This positions the first pointer n nodes ahead of the second pointer.

  6. We then move both first and second pointers simultaneously until first reaches the end of the list. This ensures that the second pointer ends up pointing to the node that needs to be removed.

  7. To remove the nth node from the end, we update the next pointer of the node pointed to by the second pointer to skip over the node to be removed.

  8. Finally, we return dummy.next, which is the modified head of the linked list without the removed node.

  9. Additionally, there are two helper functions:

    • createLinkedList(values) creates a linked list from a list of values.

    • convertToList(head) converts a linked list back into a list of values.

# Helper function to create a linked list from a list of values.
def createLinkedList(values):
    if not values:
        return None
    head = ListNode(values[0])
    current = head
    for val in values[1:]:
        current.next = ListNode(val)
        current = current.next
    return head

# Helper function to convert a linked list to a list of values.
def convertToList(head):
    result = []
    current = head
    while current:
        result.append(current.val)
        current = current.next
    return result

Let’s explain the two helper functions:

  1. createLinkedList(values): This function creates a linked list from a list of values.

    • Input: values is a list containing values that you want to insert into the linked list.

    • Output: The function returns the head of the created linked list.

    Explanation:

    • The function starts by checking if the values list is empty. If it is, it returns None to indicate an empty linked list.

    • If the values list is not empty, it creates the first node of the linked list with the value from the first element of values.

    • It then iterates through the remaining elements of values and creates new nodes for each value, connecting them together using the next attribute to form a linked list.

    • Finally, it returns the head of the linked list, which is the first node created.

  2. convertToList(head): This function converts a linked list into a list of values.

    • Input: head is the head node of the linked list that you want to convert.

    • Output: The function returns a list containing the values of the nodes in the linked list in order.

    Explanation:

    • The function starts by initializing an empty list, result, to store the values of the linked list nodes.

    • It then iterates through the linked list starting from the head node and appends the val attribute of each node to the result list.

    • The iteration continues until it reaches the end of the linked list (i.e., the next attribute of the current node becomes None).

    • After the iteration is complete, the function returns the result list, which now contains the values of all the nodes in the linked list in the same order as they appear in the linked list.

These helper functions are useful for creating linked lists from lists of values and converting linked lists back into lists of values, making it easier to work with linked list examples and test cases in a more familiar list format.

Test cases#

# Example 1
head1 = createLinkedList([1, 2, 3, 4, 5])
n1 = 2
new_head1 = removeNthFromEnd(head1, n1)
print(convertToList(new_head1))

[1, 2, 3, 5]

# Example 2
head2 = createLinkedList([1])
n2 = 1
new_head2 = removeNthFromEnd(head2, n2)
print(convertToList(new_head2))

[]

# Example 3
head3 = createLinkedList([1, 2])
n3 = 1
new_head3 = removeNthFromEnd(head3, n3)
print(convertToList(new_head3))

[1]

Certainly! Let’s analyze the time and space complexity of the removeNthFromEnd function in isolation:

Time Complexity:

  • The removeNthFromEnd function performs two passes through the linked list. In the worst case, it needs to traverse the entire linked list of length \(N\).

  • The first pass positions the first pointer \(n\) nodes ahead of the second pointer. This pass takes \(O(N)\) time because it involves iterating through all N nodes.

  • The second pass moves both first and second pointers simultaneously until first reaches the end of the list. This also takes \(O(N)\) time in the worst case.

  • Therefore, the overall time complexity of the removeNthFromEnd function is \(O(N)\).

Space Complexity:

  • The removeNthFromEnd function uses a constant amount of extra space for its variables (e.g., first, second, and dummy). This space usage does not depend on the size of the linked list.

  • The space complexity is \(O(1)\), indicating that the space used by the function is constant and independent of the size of the input linked list.

In summary, the removeNthFromEnd function has a time complexity of \(O(N)\) and a space complexity of \(O(1)\). It efficiently removes the nth node from the end of the linked list with a single pass through the list and constant extra space usage.