背景
这两天花了些时间研究了一道题目，把解题的思维过程记录一下。原题目如下：
实现一个双向链表的倒置功能（1->2->3 变成 3->2->1），请勿直接使用JDK的LinkedList。
解题
拆题
拿到这个题目后，第一感觉网上有这个题，当然，不能一上来就去搜答案，这类题旨在考验程序员的问题分析能力的，直接看了答案就没有意义了。先自己去想，实在有的点卡住了，再去搜索一些思路。而且也只去看资料中关于卡主这部分的内容，不要全篇看，以自己的思考为主。
然后我们开始分析。要想解题，首先要明白这个题是想让我们做什么。很明显，这个题包含了两个要点：
- 实现倒置（结果）
- 实现双向链表数据结构（结果依赖的前提）
实现倒置是结果，实现双向链表数据结构是依赖，那么我们从结果开始思考，将得出结果的逻辑抽象出来，然后再慢慢反推依赖。
纸笔分析
这类题有个特点，第一眼看上去会比较懵逼，生在脑子里想也比较累，所以我们可以在纸端辅助思考，用文字来捋顺自己的思路：
上图中是我的最初始的分析思路，当然，到后期编码实现时，会发现其中的step3其实是不全面的，没关系，在纸和笔分析阶段我们要写的是最直接的思路，后期会不断优化。
编码实现
在编码阶段，我是与思考阶段反着来的，我先实现了依赖，也就是先实现双向链表这个数据结构
那么，代码从哪里写起呢？我是从接口开始的，因为很明显，在JDK的标准库里，都是从接口开始的，接口对消费端提供了行为的定义。很明显，作为一个最基本的线性表应当有删增改查四个方法，然后对于双向的表来说，应当有getFirst和getLast，所以，最基本的两个接口就有了。
package com.github.since1986.learn.collection;
/**
* 线性表
*/
public interface List<E> {
void add(E element);
void add(int index, E element);
E get(int index);
void remove(E element);
void remove(int index);
int size();
}
package com.github.since1986.learn.collection;
/**
* 双向表
*/
public interface Deque<E> extends List<E> {
E getFirst();
E getLast();
}
然后我们的双向链表LinkedList应当实现双向表Deque
public class LinkedList<E> implements Deque<E>
然后再思考，我应当怎样存储双线链表中的节点呢，在这里，我其实第一开始思路有点跑偏了，由于原来我看过JDK中的ArrayList的代码，所以我总是想是不是用一个数组来存储，但是后来越想越觉得别扭，索性打开了JDK的LinkedList的代码，看了一眼，恍然大悟，其实定义一个内部的类Node，Node中包含了指向next和previous的引用，这个引用本身就构成了一个链式的结构。OK了，数据结构搞定。
//核心数据结构（不对外包暴露）
static class Node<E> {
private Node<E> previous;
private Node<E> next;
E element;
Node(Node<E> previous, Node<E> next, E element) {
this.previous = previous;
this.next = next;
this.element = element;
}
}
注意一点，这个数据结构不应被LinkedList的消费者看到，保持内聚性。
然后我们来实现add，有了add我们就能够添加测试数据了，其他有几个方法和题目无关，我们可以先放着不实现。
@Override
public void add(E element) {
if (size == 0) { //假如当前的size == 0，那么就让当前add进来的元素，生成节点成为first节点和last节点
first = last = new Node<>(null, null, element);
} else { //否则向last节点后添加一个新的节点（也就是生成一个新节点，将last节点的next指向这个新节点），让后让新的节点成为last就可以了
Node<E> newLast = new Node<>(last, null, element);
last.next = newLast;
last = newLast;
}
size++;
}
再来实现get以及其依赖的getNode
private Node<E> getNode(int index) {
if (index < 0 || index > size - 1) {
throw new IndexOutOfBoundsException();
} else if (size == 0) { //如果当前size == 0则返回null
return null;
} else if (index < size / 2) { //如果index处于list的前半部分（也就是index < size / 2）那么就从first节点开始向后找
Node<E> temp = first;
for (int i = 0; i < index; i++) {
temp = temp.next;
}
return temp;
} else { //否则，从last节点开始向前找
Node<E> temp = last;
for (int i = size - 1; i > index; i--) {
temp = temp.previous;
}
return temp;
}
}
@Override
public E get(int index) {
return getNode(index) == null ? null : getNode(index).element;
}
到这里，基本的数据结构算是实现了，我们来看一眼完整的LinkedList代码吧：
package com.github.since1986.learn.collection;
/**
* （双向）链表
*/
public class LinkedList<E> implements Deque<E> {
private int size;
private Node<E> first;
private Node<E> last;
@Override
public void add(E element) {
if (size == 0) { //假如当前的size == 0，那么就让当前add进来的元素，生成节点成为first节点和last节点
first = last = new Node<>(null, null, element);
} else { //否则向last节点后添加一个新的节点（也就是生成一个新节点，将last节点的next指向这个新节点），让后让新的节点成为last就可以了
Node<E> newLast = new Node<>(last, null, element);
last.next = newLast;
last = newLast;
}
size++;
}
@Override
public void add(int index, E element) {
//TODO 与题目无关，暂不实现
}
@Override
public E get(int index) {
return getNode(index) == null ? null : getNode(index).element;
}
@Override
public void remove(E element) {
//TODO 与题目无关，暂不实现
}
@Override
public void remove(int index) {
//TODO 与题目无关，暂不实现
}
@Override
public int size() {
return size;
}
@Override
public E getFirst() {
return getFirstNode().element;
}
@Override
public E getLast() {
return getLastNode().element;
}
//核心数据结构（不对外包暴露）
static class Node<E> {
private Node<E> previous;
private Node<E> next;
E element;
Node(Node<E> previous, Node<E> next, E element) {
this.previous = previous;
this.next = next;
this.element = element;
}
Node<E> getPrevious() {
return previous;
}
void setPrevious(Node<E> previous) {
this.previous = previous;
}
Node<E> getNext() {
return next;
}
void setNext(Node<E> next) {
this.next = next;
}
}
private Node<E> getNode(int index) {
if (index < 0 || index > size - 1) {
throw new IndexOutOfBoundsException();
} else if (size == 0) { //如果当前size == 0则返回null
return null;
} else if (index < size / 2) { //如果index处于list的前半部分（也就是index < size / 2）那么就从first节点开始向后找
Node<E> temp = first;
for (int i = 0; i < index; i++) {
temp = temp.next;
}
return temp;
} else { //否则，从last节点开始向前找
Node<E> temp = last;
for (int i = size - 1; i > index; i--) {
temp = temp.previous;
}
return temp;
}
}
Node<E> getFirstNode() {
return size == 0 ? null : getNode(0);
}
Node<E> getLastNode() {
return size == 0 ? null : getNode(size - 1);
}
void setFirstNode(Node<E> first) {
this.first = first;
}
void setLastNode(Node<E> last) {
this.last = last;
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("(null) <-> ");
Node<E> node = first;
while (node != null) {
stringBuilder.append(node.element);
stringBuilder.append(" <-> ");
node = node.next;
}
stringBuilder.append("(null)");
return stringBuilder.toString();
}
}
实现好了数据结构，我们再来实现算法倒置吧，这才是最终目标。这里注意一点，我们要实现的reverse方法不应在LinkedList中提供，因为在LinkedList语义上，提供这个方法并无意义，reverse更应该是个util类的方法，输入的是一个LinkedList，输出是倒置后的LinkedList。所以我们把这个方法封装在一个工具类里面对消费者代码提供。由于我们的reverse方法要访问LinkedList内部的Node类的API，而Node类访问是包级别的，所以我们的工具类应当同LinkedList在同一个包下定义。
来看具体代码吧，算法实现的思路写在注释里了：
package com.github.since1986.learn.collection;
public final class LinkedListUtils {
/*
* 倒置（根据高内聚的原则，这个API不应由LinkedList本身提供，因为倒置是要操作LinkedList内部API Node的，这个Node对消费者应当是不可见的，所以用了一个与LinkedList同一个包的Utils类来操作，这样就对外掩藏了Node这个API）
* 分为两个步骤：
* 第一步 交换每个节点的previous和next
* 第二步 交换LinkedList的first和last
*/
public static <E> LinkedList<E> reverse(LinkedList<E> linkedList) {
//保存原首尾节点信息，用于交换每个节点的previous和next后将LinkedList的first和last进行交换
LinkedList.Node<E> originalFirstNode = linkedList.getFirstNode();
LinkedList.Node<E> originalLastNode = linkedList.getLastNode();
//交换每个节点的previous和next
LinkedList.Node<E> originalOrderCurrentNode = originalFirstNode; //按照原顺序循环
while (originalOrderCurrentNode != null) { //按照原LinkedList的顺序循环，直至到达null（假如原LinkedList为 (null) <-> 1 <-> 2 <-> 3 <-> 4 <-> (null) 那么也就是按 1 -> 2 -> 3 -> 4 -> (null) 这样来循环，其中4后面的(null)为循环终止条件）
LinkedList.Node<E> originalPrevious = originalOrderCurrentNode.getPrevious(); //获得当前node的原previous
LinkedList.Node<E> originalNext = originalOrderCurrentNode.getNext(); //获得当前node的原next
LinkedList.Node<E> tempReference = originalOrderCurrentNode; //新建一个引用，后续的previous和next的交换在新引用上进行，不影响原LinkedList的节点，这样才能让while循环能够继续（可以想象一下，如果直接在原节点上交换，假如当前由1节点循环到了2个节点 那么 1 -> 2 -> 3交换后就变成了 3 -> 2 -> 1 ，循环的下一次等于还是1，就重复了，就不是原顺序在循环了，逻辑上是不对的）
originalOrderCurrentNode = originalNext; //让循环继续到下一节点
tempReference.setPrevious(originalNext); //将当前node的previous设置为原来的next
tempReference.setNext(originalPrevious); //将当前node的next设置为原来的previous
}
//交换LinkedList的first和last
linkedList.setFirstNode(originalLastNode);
linkedList.setLastNode(originalFirstNode);
return linkedList;
}
}
在实现倒置时，我在怎样让while循环能够继续这里卡住了，怎么想也想不通，后来看了看这篇文章中这段代码：
public DListNode reverse(DListNode head) {
DListNode curr = null;
while (head != null) {
curr = head;
head = curr.next;
curr.next = curr.prev;
curr.prev = head;
}
return curr;
}
才明白了，其实用一个中间引用就好了。另外在前面纸笔分析处我们提到了，纸笔分析中的step3并不全面，其实是少了：
//交换LinkedList的first和last
linkedList.setFirstNode(originalLastNode);
linkedList.setLastNode(originalFirstNode);
这一环节，没有这一环节倒置后每个Node虽然是正确的，但是首尾节点并不正确，后来我才想明白，实际上首尾对调后才算完成了整个链表的倒置。
好，到了这里，基本上题目就解完了。整体工程在我的GitHub里。
总结
通过这个题目，锻炼了一下自己思考/分析/解决问题的能力，同时也对JDK中的LinkedList加深了理解.
参考资料
Java标准库的LinkedList源码
