DEV Community

Prashant Mishra
Prashant Mishra

Posted on

Delete the Nth node from the end of the LinkedList

Problem

//tc:O(N) n is the length of the linked list
//sc :(1) constant
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // base case
        if(head.next ==null && n ==1) return null;
        ListNode node1 = head;
        ListNode node2 = head;
        //prev is required for edge case example if the node to be deleted is the last node of the list from start
        ListNode prev = new ListNode(0);
        prev.next = head; 
        // let node1 go ahead of node2 by n nodes
        while(n-->0){
            node1 = node1.next;
        }
        // when node1 will reach the end node then node2 will have reached the node to be delete
        while(node1!=null){
            node1 = node1.next;
            node2 = node2.next;
            prev = prev.next;
        }
        //here is the edge case what if the node to be deleted is the last node
        if(node2.next ==null){
            prev.next = node2.next; // prev of node2 will come in handy
        }
        else{
            node2.val = node2.next.val;
            node2.next = node2.next.next;
        }
        return head;
    }
}
Enter fullscreen mode Exit fullscreen mode

A more readable code ( without using the prev pointer)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //without using prev pointer
        ListNode faster = head;
        ListNode slower = head;
        while(n-->0){
            faster = faster.next;
        }
        //if faster is null then the node to be delete is the head node
        if(faster ==null) {
            return head.next;
        }
        while(faster.next!=null){
            faster = faster.next;
            slower = slower.next;
        }
        slower.next = slower.next.next;
        return head;
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)