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
Please leave a comment below if you like this post or found some error, it will help me to improve my content.

Comments

Popular Posts from this Blog

Shell Script to find sum, product and average of given numbers - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

Add two numbers in Scala - The Coding Shala

New Year Chaos Solution - The Coding Shala

Richest Customer Wealth LeetCode Solution - The Coding Shala