Python Program to Remove nth Node from Linked List

To remove the nth node from a linked list in Python, traverse the list to the (n-1)th node and adjust its next pointer to skip the nth node, e.g., use a dummy node and loop to find the node before the target, then set prev.next = prev.next.next.

Examples

InputLinked list: 1->2->3->4->5, n=2

Output1->2->3->5

InputLinked list: 10->20->30, n=1

Output20->30

InputLinked list: 5, n=1

OutputEmpty list

How to Think About It

Think of the linked list as a chain of nodes. To remove the nth node, you need to find the node just before it (the (n-1)th node) and change its link to point to the node after the nth node. If n is 1, you remove the head by moving the head pointer to the next node.

Algorithm

1

Create a dummy node pointing to the head of the list to handle edge cases easily.

2

Set a pointer to the dummy node.

3

Move the pointer (n) times to reach the node before the one to remove.

4

Change the next pointer of this node to skip the nth node.

5

Return the next of dummy node as the new head of the list.

Code

python

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

def remove_nth_from_end(head, n):
    dummy = ListNode(0, head)
    first = dummy
    second = dummy
    for _ in range(n + 1):
        first = first.next
    while first:
        first = first.next
        second = second.next
    second.next = second.next.next
    return dummy.next

def print_list(node):
    while node:
        print(node.val, end='->' if node.next else '\n')
        node = node.next

# Example usage
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
new_head = remove_nth_from_end(head, 2)
print_list(new_head)

Output

1->2->3->5

Dry Run

Let's trace removing the 2nd node from the end in the list 1->2->3->4->5.

1

Initialize dummy and pointers

dummy -> 0->1->2->3->4->5, first = dummy, second = dummy

2

Move first pointer n+1=3 steps

first moves to 1, then 2, then 3

3

Move first and second until first reaches end

first moves 4->5->None, second moves 0->1->2

4

Remove nth node by skipping

second.next (3) is skipped, second.next set to 4

5

Return new head

dummy.next points to 1->2->4->5

first.val	second.val
0	0
1	0
2	0
3	0
4	1
5	2
None	3

Why This Works

Step 1: Use a dummy node

A dummy node before the head helps handle cases where the head itself is removed without extra checks.

Step 2: Two-pointer technique

Move the first pointer n+1 steps ahead, then move both pointers until first reaches the end, so second points to the node before the target.

Step 3: Skip the nth node

Change second.next to second.next.next to remove the nth node from the list.

Alternative Approaches

Calculate length first

python

def remove_nth_from_end_length(head, n):
    length = 0
    current = head
    while current:
        length += 1
        current = current.next
    dummy = ListNode(0, head)
    current = dummy
    for _ in range(length - n):
        current = current.next
    current.next = current.next.next
    return dummy.next

This method first counts the total nodes, then removes the (length-n+1)th node; it requires two passes but is simpler to understand.

Recursive approach

python

def remove_nth_from_end_recursive(head, n):
    def recurse(node):
        if not node:
            return 0, node
        i, node.next = recurse(node.next)
        i += 1
        if i == n:
            return i, node.next
        return i, node
    _, new_head = recurse(head)
    return new_head

Uses recursion to find the nth node from the end; elegant but uses extra call stack space.

Complexity: O(L) time, O(1) space

Time Complexity

The algorithm traverses the list once with two pointers, so it runs in linear time proportional to the list length L.

Space Complexity

Only a few pointers are used, so the space complexity is constant O(1).

Which Approach is Fastest?

The two-pointer method is fastest with one pass and constant space; the length calculation method takes two passes; recursion uses extra stack space.

Approach	Time	Space	Best For
Two-pointer	O(L)	O(1)	Efficient single pass removal
Length calculation	O(L)	O(1)	Simple to understand, two passes
Recursive	O(L)	O(L)	Elegant but uses call stack