Start learning free

LESSON 428 OF 673 · LINKED LISTS

Remove Nth Node from End of List in Python (Time Complexity: O(n))

Practice O(n) Read the full explanation

You get the head of a linked list and a number n. Delete the nth node from the end. Return the head of the list.

Count from the end: the last node is the 1st.

 

Example 1:

before after 3rd from end 6 2 9 4 7 6 2 4 7

Input: head = [6,2,9,4,7], n = 3
Output: [6,2,4,7]
Explanation: The red node, 9, is the 3rd from the end.
7 is the 1st and 4 is the 2nd.
After 9 goes, 2 links straight to 4.

Example 2:

Input: head = [8,5], n = 2
Output: [5]
Explanation: The 2nd node from the end is the head.
So the new head is the node with 5.

Example 3:

Input: head = [3], n = 1
Output: []
Explanation: Deleting the only node leaves an empty list.
Return None.

 

Constraints:

  • 1 to 30 nodes.
  • Each value is between 0 and 100.
  • n is from 1 to the length of the list.

 

Follow up: Can you do it in one walk along the list, without counting its length first?

STEP 1 OF 11
    Ctrl + Enter to check

    PYTHON · LINKED LISTS

    Remove Nth Node From End Of List in Python, explained

    Understanding the Problem

    The core challenge of this problem is to efficiently remove the nth node from the end of a singly linked list. This problem is significant in various applications such as managing playlists, task scheduling, and more. A common pitfall is misunderstanding the position of the nth node from the end, especially in edge cases like when the list has only one node.

    Approach

    To solve this problem, we can use a two-pointer technique to achieve a one-pass solution. Here's a step-by-step approach:

    Naive Solution

    The naive solution involves two passes through the list:

    1. First, traverse the list to count the total number of nodes.
    2. Then, traverse the list again to find the (total - n + 1)th node from the beginning and remove it.

    This approach is not optimal as it requires two passes through the list, resulting in a time complexity of O(2n).

    Optimized Solution

    The optimized solution uses a two-pointer technique to achieve the task in one pass:

    1. Initialize two pointers, both starting at the head of the list.
    2. Move the first pointer n steps ahead.
    3. Then, move both pointers simultaneously until the first pointer reaches the end of the list.
    4. At this point, the second pointer will be at the (total - n)th node, just before the node to be removed.
    5. Adjust the pointers to remove the nth node from the end.

    Algorithm

    Here is a step-by-step breakdown of the optimized algorithm:

    1. Create a dummy node that points to the head of the list. This helps handle edge cases where the head needs to be removed.
    2. Initialize two pointers, both pointing to the dummy node.
    3. Move the first pointer n+1 steps ahead to maintain a gap of n nodes between the two pointers.
    4. Move both pointers simultaneously until the first pointer reaches the end of the list.
    5. The second pointer will now be just before the node to be removed. Adjust its next pointer to skip the target node.
    6. Return the next node of the dummy node as the new head of the list.

    Code Implementation

    class ListNode:
        def __init__(self, val=0, next=None):
            self.val = val
            self.next = next
    
    def removeNthFromEnd(head: ListNode, n: int) -> ListNode:
        # Create a dummy node that points to the head
        dummy = ListNode(0, head)
        first = dummy
        second = dummy
        
        # Move the first pointer n+1 steps ahead
        for _ in range(n + 1):
            first = first.next
        
        # Move both pointers until the first pointer reaches the end
        while first:
            first = first.next
            second = second.next
        
        # Remove the nth node from the end
        second.next = second.next.next
        
        # Return the new head of the list
        return dummy.next
    

    Complexity Analysis

    The time complexity of the optimized solution is O(n), where n is the number of nodes in the list. This is because we only traverse the list once. The space complexity is O(1) as we are using a constant amount of extra space.

    Edge Cases

    Consider the following edge cases:

    • Single node list: Removing the only node should return an empty list.
    • Removing the head node: The dummy node helps handle this case seamlessly.
    • n equals the length of the list: The dummy node ensures the correct node is removed.

    Testing

    To test the solution comprehensively, consider the following test cases:

    def print_list(head):
        result = []
        while head:
            result.append(head.val)
            head = head.next
        return result
    
    # Test case 1
    head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
    n = 2
    print(print_list(removeNthFromEnd(head, n)))  # Output: [1, 2, 3, 5]
    
    # Test case 2
    head = ListNode(1)
    n = 1
    print(print_list(removeNthFromEnd(head, n)))  # Output: []
    
    # Test case 3
    head = ListNode(1, ListNode(2))
    n = 1
    print(print_list(removeNthFromEnd(head, n)))  # Output: [1]
    

    Thinking and Problem-Solving Tips

    When approaching such problems, consider the following tips:

    • Understand the problem requirements and constraints thoroughly.
    • Think about edge cases and how to handle them.
    • Break down the problem into smaller steps and solve each step methodically.
    • Practice similar problems to improve problem-solving skills and familiarity with common patterns.

    Conclusion

    In this blog post, we discussed how to remove the nth node from the end of a linked list efficiently using a two-pointer technique. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for developing strong problem-solving skills in computer science.

    Additional Resources

    For further reading and practice, consider the following resources:

    Keep going with Python650+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free