今天的面试中有一个比较有意思的题目,其实应该主要还是考察思路吧,可能是链表有比较长的时间没有看了,感觉问了下被问得有点懵。 要实现的东西就是在链表中实现从链表的后面取倒数第二个元素。 * 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…