//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;
}
}
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;
}
}
Top comments (0)