Find n'th node from the end of a Linked List - GeeksforGeeks
Given a Linked List and a number n, write a function that returns the value at the n'th node from end of the Linked List.
public static LinkedListNode nthToLast(LinkedListNode head, int k) {
LinkedListNode p1 = head;
LinkedListNode p2 = head;
/* Move p1 k nodes into the list.*/
for (int i = 0; i < k; i++) {
if (p1 == null) return null; // Out of bounds
p1 = p1.next;
}
/* Move them at the same pace. When p1 hits the end,
* p2 will be at the right element. */
while (p1 != null) {
p1 = p1.next;
p2 = p2.next;
}
return p2;
}
https://github.com/careercup/CtCI-6th-Edition/blob/master/Java/Ch%2002.%20Linked%20Lists/Q2_02_Return_Kth_To_Last/QuestionA.java
public static int printKthToLast(LinkedListNode head, int k) {
if (head == null) {
return 0;
}
int index = printKthToLast(head.next, k) + 1;
if (index == k) {
System.out.println(k + "th to last node is " + head.data);
}
return index;
}
public static LinkedListNode kthToLast(LinkedListNode head, int k) {
Index idx = new Index();
return kthToLast(head, k, idx);
}
public static LinkedListNode kthToLast(LinkedListNode head, int k, Index idx) {
if (head == null) {
return null;
}
LinkedListNode node = kthToLast(head.next, k, idx);
idx.value = idx.value + 1;
if (idx.value == k) {
return head;
}
return node;
}
Read full article from Find n'th node from the end of a Linked List - GeeksforGeeks
Given a Linked List and a number n, write a function that returns the value at the n'th node from end of the Linked List.
https://github.com/careercup/CtCI-6th-Edition/blob/master/Java/Ch%2002.%20Linked%20Lists/Q2_02_Return_Kth_To_Last/QuestionD.java
public static LinkedListNode nthToLast(LinkedListNode head, int k) {
LinkedListNode p1 = head;
LinkedListNode p2 = head;
/* Move p1 k nodes into the list.*/
for (int i = 0; i < k; i++) {
if (p1 == null) return null; // Out of bounds
p1 = p1.next;
}
/* Move them at the same pace. When p1 hits the end,
* p2 will be at the right element. */
while (p1 != null) {
p1 = p1.next;
p2 = p2.next;
}
return p2;
}
https://github.com/careercup/CtCI-6th-Edition/blob/master/Java/Ch%2002.%20Linked%20Lists/Q2_02_Return_Kth_To_Last/QuestionA.java
public static int printKthToLast(LinkedListNode head, int k) {
if (head == null) {
return 0;
}
int index = printKthToLast(head.next, k) + 1;
if (index == k) {
System.out.println(k + "th to last node is " + head.data);
}
return index;
}
public static LinkedListNode kthToLast(LinkedListNode head, int k) {
Index idx = new Index();
return kthToLast(head, k, idx);
}
public static LinkedListNode kthToLast(LinkedListNode head, int k, Index idx) {
if (head == null) {
return null;
}
LinkedListNode node = kthToLast(head.next, k, idx);
idx.value = idx.value + 1;
if (idx.value == k) {
return head;
}
return node;
}
Read full article from Find n'th node from the end of a Linked List - GeeksforGeeks