面试问题之链表（LinkedList）

今天的面试中有一个比较有意思的题目，其实应该主要还是考察思路吧，可能是链表有比较长的时间没有看了，感觉问了下被问得有点懵。

要实现的东西就是在链表中实现从链表的后面取倒数第二个元素。

编辑

 * 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<Integer> 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<Integer> 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 < 1 || k > this.lenght()) {return null;}Node p1 = head;Node p2 = head;for (int i = 0; i <= k; i++)p1 = p1.next;while (p1 != null) {p1 = p1.next;p2 = p2.next;}return p2;}

可以认为我们 p1 定义的是第一个指针计数器， p2 是第二个指针计数器。

编辑

所以通过双指针的方法，只需要一个循环就可以完成上面的算法了。直接把 P2 输出就好了

需要注意的是，因为要求是返对应移动 2 步的下标。

所以上面第一步的 For 循环应该是 i<=k ，而不是 j<k，不过这个地方的代码比较调试，没太大问题。

就是这里需要注意下。