03、数据结构和算法 - 实战：图解单向链表反转
所谓的单链表反转，就是把每个节点的指针域由原来的指向下一个节点变为指向其前一个节点。
一直觉得反转链表实现代码不是很好理解，今天用画图的方式去理解它。
1.1 需求分析
1、 反转链表需求：；
- 输入：[HBase,Redis,Kafka]
- 输出：[Kafka,Redis,HBase]
2、 分析：；
存在链表 HBase → Redis → Kafka → N，我们想要把它改成 N ← Kafka ← Redis ← HBase。
先说下思路：由于单链表没有指向前一个节点的指针域，因此我们需要增加一个指向前一个节点的指针prevNode，用于存储每一个节点的前一个节点。此外，还需要定义一个保存当前节点的指针currentNode，以及下一个节点的nextNode。定义好这三个指针后，遍历单链表，将当前节点的指针域指向前一个节点，之后将定义三个指针往后移动，直至遍历到最后一个节点停止。
链表反转代码的实现:
public CustomLinkedList reverse() {
Node<E> currentNode = this.first; //1
Node<E> prevNode = new Node<E>(); //2
while (currentNode != null) {
//3
Node<E> nextNode = currentNode.next; //4
currentNode.next = prevNode.next; //5
prevNode.next = currentNode; //6
currentNode = nextNode; //7
}
CustomLinkedList customLinkedList = new CustomLinkedList(); //#8
customLinkedList.first = prevNode.next; //#9
customLinkedList.size = this.size; //#10
return customLinkedList;
}
1.2 图解链表反转
1、 链表就有HBase,Redis,Kafka个元素，后面还跟着一个null，待反转的链表如下：；
- 第一行【#1】代码图解：
Node<E> currentNode = this.first; //1
- 第二行【#2】代码图解：
Node<E> prevNode = new Node<E>(); //2
-
第三行【#3】代码图解，循环部分核心代码图解：
-
循环部分是链表反转的核心部分，我们先走一遍循环，图解分析一遍。因为currentNode指向了first，first不为null，所以进入循环。
while (currentNode != null) {
//3
Node<E> nextNode = currentNode.next; //4
currentNode.next = prevNode.next; //5
prevNode.next = currentNode; //6
currentNode = nextNode; //7
}
- 第四行【#4】代码图解：
Node<E> nextNode = currentNode.next; //4
- 第五行【#5】代码图解：
currentNode.next = prevNode.next; //5
把prevNode.next赋值给currentNode.next,因为prevNode.next初始化指向null，即currentNode.next(节点[Hbase])指向了null，链表图解成这样了：
- 第六行【#6】代码图解：
把currentNode赋值给prevNode.next，prevNode.next指向currentNode。
prevNode.next = currentNode; //6
- 第七行【#7】代码图解：
把nextNode赋值给currentNode，即currentNode指向nextNode，图解如下：
currentNode = nextNode; //7
至此，第一遍循环执行结束，回到while循环条件，currentNode依旧不为null，我们继续图解完它。
1.3 第二次循环图解
随着深入图解 4-7 行代码又执行一遍，依次可得图：
Node<E> nextNode = currentNode.next; //4
currentNode.next = prevNode.next; //5
prevNode.next = currentNode; //6
currentNode = nextNode; //7
- 第四行【#4】代码图解：
Node<E> nextNode = currentNode.next; //4
在执行完第四行代码后，可得如下图：
- 第五行【#5】代码图解：
currentNode.next = prevNode.next; //5
- 第六行【#6】代码图解：
prevNode.next = currentNode; //6
- 第七行【#7】代码图解：
currentNode = nextNode; //7
至此，第二遍循环执行结束，回到while循环条件，currentNode依旧不为null，我们继续图解完它。
1.4 第三次循环图解
来到这里，currentNode依旧不为null，再回到while循环，再执行一遍：
Node<E> nextNode = currentNode.next; //4
currentNode.next = prevNode.next; //5
prevNode.next = currentNode; //6
currentNode = nextNode; //7
- 第四行【#4】代码图解：
Node<E> nextNode = currentNode.next; //4
在执行完第四行代码后，可得如下图：
- 第五行【#5】代码图解：
currentNode.next = prevNode.next; //5
- 第六行【#6】代码图解：
prevNode.next = currentNode; //6
- 第七行【#7】代码图解：
currentNode = nextNode; //7
来到这里，我们发现currentNode已经为null了，可以跳出循环了。
1.5 代码封装
第八行到第十行代码，#8-#9-#10，是为了封装给外部使用
CustomLinkedList customLinkedList = new CustomLinkedList(); //#8
customLinkedList.first = prevNode.next; //#9
customLinkedList.size = this.size; //#10
return customLinkedList;
1.6 测试反转后的链表
简单测试，在main()方法中，添加[HBase,Redis,Kafka]数据，打印反转后的结果。
public static void main(String[] args) {
CustomLinkedList customLinkedList = new CustomLinkedList();
customLinkedList.addFirst("Kafka");
customLinkedList.addFirst("Redis");
customLinkedList.addFirst("HBase");
System.out.println("原始链表节点元素：" + customLinkedList);
CustomLinkedList reverseCustomLinkedList = customLinkedList.reverse();
System.out.println("反转后链表节点元素：" + reverseCustomLinkedList);
}
执行结果：
原始链表节点元素：[HBase,Redis,Kafka]
反转后链表节点元素：[Kafka,Redis,HBase]