Showing posts with label N'th node from the end of a Linked List. Show all posts
Showing posts with label N'th node from the end of a Linked List. Show all posts ## N'th node from the end of a Linked List

Need to find the N'th node from the end of Singly Linked List. Since its singly linked we can't traverse bidirectional and important condition is to traverse only once from start to end of the Linked List. Suppose if the length of Linked List is less than N then return -1.

Solution:
> Use 2 pointers where 1st pointer will be traversing from start to end and 2nd pointer will be starting when 1st pointer reaches N'th node.
> In such a way that when 1st pointer reaches the last node in Linked List 2nd pointer will be placed in the N'th node from last.

Let see simple Java code to implement LinkedList and to find the N'th node from last just by traversing only once.

```public class FindLLNode {

int data;

this.data = data;
this.next = null;
}
}

public static void main(String[] args) {

int val[] = new int[] { 23, 7, 10, 45, 9, 11 };

int findNode = 3;

FindLLNode obj = new FindLLNode();

int nthNodeVal = obj.findLLNode(start, findNode);

System.out.println("nth Node Value from last : " + nthNodeVal);
}

LinkedList start = null, temp = null;
for (int i : val) {

if (start == null) {
start = temp = node;
} else {
temp.next = node;
temp = temp.next;
}
}
return start;
}

private int findLLNode(LinkedList start, int findNode) {

LinkedList p1 = start, p2 = start;
int i = 0;
boolean flag = false;
while (p1 != null) {
if (i >= findNode) {
p2 = p2.next;
flag = true;
}
p1 = p1.next;
i++;
}
if (!flag)
return -1;
return p2.data;
}
}
```

OUTPUT:

```3rd Node Value from last : 45
```