← Linked Lists

Remove Nth From End

Medium
Python
def remove_nth_from_end(head,n):
    dummy=type('N',(),{'val':0,'next':head})()
    fast=slow=dummy
    for _ in range(n+1): fast=fast.next
    while fast: slow=slow.next; fast=fast.next
    slow.next=slow.next.next
    return dummy.next
Java
public ListNode removeNthFromEnd(ListNode head,int n){
    ListNode dummy=new ListNode(0); dummy.next=head;
    ListNode fast=dummy,slow=dummy;
    for(int i=0;i<=n;i++) fast=fast.next;
    while(fast!=null){slow=slow.next;fast=fast.next;}
    slow.next=slow.next.next;
    return dummy.next;
}

Key Insight

n+1 gap technique. range(n+1) vs i<=n.

Python → Java Differences

  • range(n+1) vs i<=n
  • Gap technique identical
  • Dummy head pattern
Python
def remove_nth_from_end(head,n):
    dummy=type('N',(),{'val':0,'next':head})()
    fast=slow=dummy
    for _ in range(n+1): fast=fast.next
    while fast: slow=slow.next; fast=fast.next
    slow.next=slow.next.next
    return dummy.next
Java
public ListNode removeNthFromEnd(ListNode head,int n){
    ListNode dummy=new ListNode(0); dummy.next=head;
    ListNode fast=dummy,slow=dummy;
    for(int i=0;i<=n;i++) fast=fast.next;
    while(fast!=null){slow=slow.next;fast=fast.next;}
    slow.next=slow.next.next;
    return dummy.next;
}

Algorithm Steps

1. Create gap of n+1
2. Move both until fast null
3. Remove slow.next
← Previous All Linked Lists Next →