java面试问题之链表（LinkedList）_Java教程

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

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

 * 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 < 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

就是这里需要注意下。