Hi friends, in this article we going to see how to remove the Nth node from end of the list. Here is our given problem,

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

Given n will always be valid.

Follow up:

Could you do this in one pass?

Before moving into the solution, I ask, you guys try to come up with your own approach. Take 5 to 10 minutes time, try to solve the problem.

If you really has done, I appreciate your work, you are great😇

Basic knowledge

  1. Linked List CRUD Operations
  2. Rotate the List
  3. How to remove elements from List

How can we APPROACH this problem?

In our given question, they mentioned Could you do this in one pass? That is we have to solve this problem with O(n) time complexity.

BEst way

  1. Slow and Fast Pointer Approach

Do you know?

If you know Slow and Fast Pointer approach, you can able to solve most of the Linked List Problems easily.

See my previous articles, I have solved most of the linked list problems in O(n) time complexity with Slow and Fast pointer approach.

Steps to Solve

Input: 

head = 1->2->3->4->5->null
n = 2;

Create a dummy newHead node

ListNode newHead = new ListNode(0);
newHead = 0->null;

Assign head, next to the newHead

newHead.next = head;
newHead = 0>1->2->3->4->5->null;

Assign newHead node to the fast and slow pointers

ListNode fast = newHead;
fast = 0->1->2->3->4->5->null;

ListNode slow = newHead;
slow = 0->1->2->3->4->5->null;

Now move fast pointer 0 to n positions, so that the gap between slow and fast becomes n

while(n > 0)
{
   fast = fast.next;
   n--;
}

In our case, n = 2

Iteration first time, n = 2

fast = fast.next;
fast = 1->2->3->4->5->null;

n--;
n = 1;


Iteration second time, n = 1

fast = fast.next;
fast = 2->3->4->5->null;

n--;
n = 0;

Iteration third time, n = 0
Since n is equal to 0, it breaks and comes out of the while loop. 

Still now we have,

fast = 2->3->4->5->null;
slow = 0->1->2->3->4->5->null;

We maintained a gap between fast and slow is n.

Now, move fast and slow pointer simultaneously, still fast.next becomes null;

It indicates that, when fast.next becomes null, slow pointer is standing infront of the nth node.

Therefore, slow.next = slow.next.next;
By assigning slow’s next’s next pointer to slow’s next, removes the nth node.

while(fast.next != null)
{
  fast = fast.next;
  slow = slow.next;
}
In our case, 
fast = 2->3->4->5->null;
slow = 0->1->2->3->4->5->null;

Iteration first time, fast.next != null
fast = fast.next;
fast = 3->4->5->null;

slow = slow.next;
slow = 1->2->3->4->5->null;


Iteration second time, fast.next != null
fast = fast.next;
fast = 4->5->null;

slow = slow.next;
slow = 2->3->4->5->null;



Iteration third time, fast.next != null
fast = fast.next;
fast = 5->null;

slow = slow.next;
slow = 3->4->5->null;



Iteration fourth time, fast.next == null.
Breaks the condition, comes out of the while loop. 

Still now we have,

fast = 5->null;
slow = 3->4->5->null;
slow.next = slow.next.next;
By assigning slow's next's next pointer to slow's next, removes the nth node. 

slow = 3->5->null;

Hence, we remove the nth node.

Already, slow pointer reference is with newHead.
newHead = 0->1->2->3->5->null;

When I return, newHead.next, I will get my desired list

Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        
        ListNode newHead = new ListNode(0);
        
        newHead.next = head;
        
        ListNode fast = newHead;
        ListNode slow = newHead;
        
        while(n > 0)
        {
            fast = fast.next;
            n--;
        }
        
        while(fast.next != null)
        {
            slow = slow.next;
            fast = fast.next;
        }
        
        slow.next = slow.next.next;
        
        return newHead.next;
    }
}


Time Complexity : O(n)

Space Complexity: O(1)

Note: I love to teach programming in simple and fun way. I’m consistently making algorithms and data structures tutorials here. To get newsletter and notification of my new articles, please follow my blog via email. This is not spam, I’m a Full Stack Web Developer working in a Good product based company, Coimbatore.

Join 1,271 other followers

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s