Posts Remove Nth Node From End of List
Post
Cancel

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.

leetcode

SOLUTION

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {

    public int getListSize(ListNode node){
        int size = 0;
        while(node!=null){
            size++;
            node=node.next;
        }
        return size;
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
            
        int size = getListSize(head);
        int k = (size-n); 

        if(k == 0) return head.next;

        ListNode temp = head;

        while(k>1 && head !=null){
            k--;
            temp = temp.next;
        }

        if(temp.next != null)
            temp.next = temp.next.next;

        return head;

    }
}

Another way to code using Dummy head (Two Pass)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {

    public int getListSize(ListNode node){
        int size = 0;
        while(node!=null){
            size++;
            node=node.next;
        }
        return size;
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {

        int size = getListSize(head);

        int k = size-n+1; //kth node from the start

        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;

        ListNode temp = dummyHead;

        while(k>1 && temp != null){
            k--;
            temp = temp.next;
        }

        temp.next = temp.next.next;

        return dummyHead.next;
        
    }
}

Optimization (Single Pass | Two Pointers)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {

    public ListNode removeNthFromEnd(ListNode head, int n) {

        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;

        ListNode t1 = dummyHead;
        ListNode t2 = dummyHead;

        //Move t1 N steps ahead
        for(int i=0; i<n; i++){
            t1 = t1.next;
        }

        //Keep moving t1 and t2 until t1 reaches last Node in the list
        //At that point, t2 will be before the Node which needs to be removed
        while(t1.next != null){
            t1 = t1.next;
            t2 = t2.next;
        }

        t2.next = t2.next.next;

        return dummyHead.next;
        
    }
}
This post is licensed under CC BY 4.0 by the author.