Given a linked list, remove the nth node from the end of the list and return its head.
For 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.
Given n will always be valid.
Try to do this in one pass.
package askgif.linkedlist;
class ListNode{
public int data;
public ListNode next;
};
public class NNodeFromLast {
public static void main(String[] args) {
ListNode node1 = new ListNode();
ListNode node2 = new ListNode();
ListNode node3 = new ListNode();
ListNode node4 = new ListNode();
node1.data = 1;
node2.data = 2;
node3.data = 3;
node4.data = 4;
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = null;
int n = 2;
System.out.println(FindNNodeFromLast(node1,n));
}
private static int FindNNodeFromLast(ListNode ll, int num) {
ListNode temp = ll;
int i = 0;
while(true){
if(temp == null)
return 0;
if(i == num){
break;
}
++i;
temp = temp.next;
}
while(true) {
if(temp == null)
return ll.data;
temp = temp.next;
ll = ll.next;
}
}
}
The time complexity of the above solution is O(n) as we are iterating through the linked list only once.
