今天的面试中有一个比较有意思的题目，其实应该主要还是考察思路吧，可能是链表有比较长的时间没有看了，感觉问了下被问得有点懵。
要实现的东西就是在链表中实现从链表的后面取倒数第二个元素。
* Assuming we have the following list: 1 → 2→ 3 → 4 → 5 → 6 → 7
* And a number k = 2
ArrayList 实现
如果不考虑数据结构，不管你是用 List 还是 ArrayList 还是 LinkedList 都很好实现的。
Integer k = 2;
List inputList = new ArrayList();
inputList.add(1);
inputList.add(2);
inputList.add(3);
inputList.add(4);
inputList.add(5);
inputList.add(6);
inputList.add(7);
log.debug("{}", inputList.get(inputList.size() - k - 1));
使用List Size 的方法，从后面返回。
List 反转方法
下面可以用 List 反转的方法来做。
Collections 中有一个反转的方法，可以直接把 List 反转。
Integer k = 2;
List inputList = new ArrayList();
inputList.add(1);
inputList.add(2);
inputList.add(3);
inputList.add(4);
inputList.add(5);
inputList.add(6);
inputList.add(7);
Collections.reverse(inputList);
log.debug("{}", inputList.get(k));
自定义链表
下面就来说说自定义链表的方式来做这个了。
感觉这个就应该面试的人希望做的吧。
创建链表数据结构
首先我们需要定义链表数据结构，因为很长时间没有弄链表了，差不多自己都忘记了。说心里话当时都没有想出来怎么自定义链表。
在这里，我们可以定义一个单向链表，我们也可以定义一个双向链表。
非常非常重要的是，在定义完成 Node 后，我们还需要定义一个 head，这个 head 是 Node 对象。
在做题的时候，这个地方忘记了。
所以完整的定义应该是下面的代码：
Node head = null;
public class Node {
public Integer data;
public Node prev;
public Node next;
public Node(int data) {
this.data = data;
}
public Integer getValue() {
return this.data;
}
}
因为是单向链表，所以上面我们定义的 Node prev 其实是没有什么意义的。
添加元素方法
当数据结构定义后，下一步就应该是要添加元素了。
所以我们需要一个添加 Node 节点的方法。
方法的代码如下：
public void addNode(int d) {
Node newNode = new Node(d);
if (head == null) {
head = newNode;
return;
}
Node tmp = head;
while (tmp.next != null) {
tmp = tmp.next;
}
tmp.next = newNode;
}
这个方法是无返回的。
首先初始化一个 Node 对象，然后检查 head 是否为 null。
如果 head 为 Null，那么就把这个新初始化的对象放到 head 中。
如果 head 不为 Null，那么就遍历链表，找到链表的末尾添加上去。
获得链表长度
这个方法你可能不需要，但是有可能有助于帮助你链表的初始化情况。
获得长度就非常简单了。
对链表进行遍历到链表的末尾，如果为 null 的话，就返回计数器。
方法如下：
public int lenght() {
int lenght = 0;
Node tmp = head;
while (tmp != null) {
lenght++;
tmp = tmp.next;
}
return lenght;
}
返回从后面数的元素。
这个地方有很多方法可以实现，你可以把链表放入到 List 后，然后遍历。
你也可以实现一个 Get 下标元素的方法，这个时候你就需要上面我们写的 Get List 长度的方法了。
这个方法是后来我考古找到的，其实如果是大学生的话，这个方法老师应该说过。
双指针步进式查找法。
完整代码如下：
public Node moveSteps(Node head, int k) {
if (k this.lenght()) {
return null;
}
Node p1 = head;
Node p2 = head;
for (int i = 0; i
