面试问题之链表 （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

就是这里需要注意下。

总结

说心里话，这个题目真正在代码平台上，答得并不是很好。

总结下就是对链表应该是知道怎么表达的，具体的写法应该还是明白的，问题就在于后面的反转算法上。

在大部分情况下，我们应该都会用的是 Size 减去需要移动的步数，或者是想到的是 List 反转，这是因为 JDK 已经提供了 Collections.reverse(inputList); 方法了。

并不认为实现这个方法的难度在那里，但是更主要的是想问下对数据结构或者链表这个数据结构熟不熟悉吧。

如果你不经常用，可能不熟悉，大部分情况下你可能用的是 ArrayList，真正用 LinkedList 的时候不多。

很多人应该都没有选择障碍综合症，直接 ArrayList。

最后，参与面试的人问了还有没有其他办法吗？除了获得 List 总数后 get value

我想了下，可能还有就是用 HashMap， Key 是数字序列，Value 是 Node 对象。

这个也还是需要遍历一次链表，当然对这个问题也是可行的，到最后你就直接 Get(K) 就行了。也不是不可以。

链表

链表的这个问题，在这几年的面试中，被问到了 2 回，很多公司有点喜欢拿链表说事。

这也无可厚非，链表这东西本身比较冷门，如果你在找工作之前没有认真看看或者想起来链表怎么存和在 Java 的代码中是怎么实现的话可能才上来就会有点懵的。

建议是，找工作的小朋友还是需要看看链表的这个数据结构的，感觉这个数据结构在很多面试的时候都会问到。

Solution.java (2.0 KB)

上面我就把这个问题的解答给贴上来了。

虽然题目没有完全做出来，还是有点遗憾。

IT 这个行业已经有点开始卷得让人不知道要做什么了，真正业务上面的没人做，程序上面很多时候都要做算法，一些算法是比较难在 30 分钟内写出来并且实现的。

每次面试，千万都不要太当回事情，有时候更多的是一种缘分。

如果有缘分的话，一切水到渠成。

对每次面试多总结下，总会有所进步的。感觉这次面试的时候面试的人自己也没有在上面调试过代码，否则我们还花了点时间在编译器错误上面。

这样说吧，我并不认为每次给你面试的人都会认真自己把代码跑通，上面的这个问题，我相信如果是我去面试别人的话，我先要把自己的的代码跑通，这样在别人写代码的时候，我也能够及时的帮助别人纠正语法错误。

也许，这就是现在所有 OA 的现状吧，OA 你的人自己代码都没有完整跑通过。哈哈。

面试问题之链表 （LinkedList） - 求职路上 - iSharkFly