First of all
As mention in comment, but to be more clear, the question is from:
<Cracking the coding interview 6th> | IX Interview Questions | 2. Linked Lists | Question 2.2.
It's a great book by Gayle Laakmann McDowell, a software engineer from Google, who has interviewed a lot people.
Approaches
(Assuming the linked list doesn't keep track of length), there are 2 approaches in O(n) time, and O(1) space:
- Find length first, then loop to the (len-k+1) element.
This solution is not mentioned in the book, as I remember.
- Loop, via 2 pointer, keep them (k-1) distance.
This solution is from the book, as the same in the question.
Code
Following is the implementation in Java, with unit test, (without using any advanced data structure in JDK itself).
KthToEnd.java
/**
* Find k-th element to end of singly linked list, whose size unknown,
* <p>1-th is the last, 2-th is the one before last,
*
* @author eric
* @date 1/21/19 4:41 PM
*/
public class KthToEnd {
/**
* Find the k-th to end element, by find length first.
*
* @param head
* @param k
* @return
*/
public static Integer kthToEndViaLen(LinkedListNode<Integer> head, int k) {
int len = head.getCount(); // find length,
if (len < k) return null; // not enough element,
return (Integer) head.getKth(len - k).value; // get target element with its position calculated,
}
/**
* Find the k-th to end element, via 2 pinter that has (k-1) distance.
*
* @param head
* @param k
* @return
*/
public static Integer kthToEndVia2Pointer(LinkedListNode<Integer> head, int k) {
LinkedListNode<Integer> p0 = head; // begin at 0-th element,
LinkedListNode<Integer> p1 = head.getKth(k - 1); // begin at (k-1)-th element,
while (p1.next != null) {
p0 = p0.next;
p1 = p1.next;
}
return p0.value;
}
static class LinkedListNode<T> {
private T value;
private LinkedListNode next;
public LinkedListNode(T value) {
this.value = value;
}
/**
* Append a new node to end.
*
* @param value
* @return new node
*/
public LinkedListNode append(T value) {
LinkedListNode end = getEnd();
end.next = new LinkedListNode(value);
return end.next;
}
/**
* Append a range of number, range [start, end).
*
* @param start included,
* @param end excluded,
*/
public void appendRangeNum(Integer start, Integer end) {
KthToEnd.LinkedListNode last = getEnd();
for (int i = start; i < end; i++) {
last = last.append(i);
}
}
/**
* Get end element of the linked list this node belongs to, time complexity: O(n).
*
* @return
*/
public LinkedListNode getEnd() {
LinkedListNode end = this;
while (end != null && end.next != null) {
end = end.next;
}
return end;
}
/**
* Count of element, with this as head of linked list.
*
* @return
*/
public int getCount() {
LinkedListNode end = this;
int count = 0;
while (end != null) {
count++;
end = end.next;
}
return count;
}
/**
* Get k-th element from beginning, k start from 0.
*
* @param k
* @return
*/
public LinkedListNode getKth(int k) {
LinkedListNode<T> target = this;
while (k-- > 0) {
target = target.next;
}
return target;
}
}
}
KthToEndTest.java
(unit test, using TestNG, or you change to JUnit / .., as wish)
import org.testng.Assert;
import org.testng.annotations.BeforeClass;
import org.testng.annotations.Test;
/**
* KthToEnd test.
*
* @author eric
* @date 1/21/19 5:20 PM
*/
public class KthToEndTest {
private int len = 10;
private KthToEnd.LinkedListNode<Integer> head;
@BeforeClass
public void prepare() {
// prepare linked list with value [0, len-1],
head = new KthToEnd.LinkedListNode(0);
head.appendRangeNum(1, len);
}
@Test
public void testKthToEndViaLen() {
// validate
for (int i = 1; i <= len; i++) {
Assert.assertEquals(KthToEnd.kthToEndViaLen(head, i).intValue(), len - i);
}
}
@Test
public void testKthToEndVia2Pointer() {
// validate
for (int i = 1; i <= len; i++) {
Assert.assertEquals(KthToEnd.kthToEndVia2Pointer(head, i).intValue(), len - i);
}
}
}
Tips:
KthToEnd.LinkedListNode
It's a simple singly linked list node implemented from scratch, it represents a linked list start from itself.
It doesn't additionally track head / tail / length, though it has methods to do that.
