Remove Nth Node From End of Linked List Java Program - The Coding Shala

Home >> Interview Questions >> Remove Nth node from the end of linked list

Remove Nth Node From End of Linked List

Problem:

Given a linked list, remove the n-th node from the end of the 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.

Remove Nth Node from the end of Linked List Java Program

Approach 1:

We can remove the length-n+1 node. For this, we need to find out the length of the given linked list. To remove the nth node from the end of the list will take two passes.

Java Code 

/**
 * 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 tmp = head;
        int len = 0;
        while(tmp != null){
            len++;
            tmp = tmp.next;
        }
        
        n = len-n;
        tmp = head;
        while(n>1) { tmp = tmp.next; n--; }
        if(n == 0) head = head.next;
        else if(tmp.next.next != null){
            tmp.next = tmp.next.next;
        }else tmp.next = null;
        return head;
    }
}

Approach 2:

We can do the same using two pointers. The fast pointer should be n place ahead from slow pointer and when the fast pointer reaches to the null remove the next node to slow pointer.

Java Code 

/**
 * 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 dummy = new ListNode(0);
        dummy.next = head;
        ListNode slow = dummy;
        ListNode fast = dummy;
        while(n>=0){
            fast = fast.next;
            n--;
        }
        while(fast != null){
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}

Other Posts You May Like

• Intersection of two linked list
• Detect cycle in a linked list
• Reverse a linked list
• Find First Node of a cycle in a linked list
• Merge Two Sorted linked list

Please leave a comment below if you like this post or found some error, it will help me to improve my content.