java 反转链表
知乎上看到的一个问题。虽然比较简单，还是把解题思路记录一下。
参考：https://www.zhihu.com/question/27090581
一、问题
https://discuss.leetcode.com/category/214/reverse-linked-list
Reverse a singly linked list.
|
1 |
1 -> 2 -> 3 -> 4 -> 5 |
to
|
1 |
5 -> 4 -> 3 -> 2 -> 1 |
二、解题思路
这题没有强调一定要在原链表内操作。我们完全可以把链表中的所有元素取出来，放在数组（或者其他容器）中，再自行构造一条新的链表，一样能达到题目效果。
问题是，这种做法需要借助外部空间，需要遍历一次链表，再遍历一次数组容器，效率不高，需要另外的解法。
（1）直观的解法
我一开始想到的是比较直观的解法：
获取头结点后，首先记录头结点的下一个节点（作为下个操作的节点），然后把头结点的指向改成头结点的上一个节点（反转当前节点的指向），之后把当前操作对象记录下来（用于给下个节点的指向留下记录），最后把头结点换成下一个操作的节点（重复此过程）。
ReverseLinkedList.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
public static Node reverse1(Node head) { Node pre = null; while (head != null) { Node next = head.next; // 记录下个操作节点 head.next = pre; // 反转当前节点的指向 pre = head; // 记录当前节点，给下个操作节点的指向做准备 head = next; // 更新当前节点为下个节点，循环此过程 } return pre; } |
（2）递归解法
参考leetcode上的discuss。
我尝试理解了一下这个算法：
首先获取链表的头结点，记录头结点的下一个节点（作为下个操作的节点），然后立刻递归反转下一个节点。具体的反转操作为：让下一个节点指向当前节点，然后把当前节点的指向置为空（避免出现死循环，同时保证最后一个节点指向为null）。
ReverseLinkedList.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
public static Node reverse2(Node head) { if (head == null || head.next == null) return head; Node nextNode = head.next; Node newHead = reverse2(nextNode); nextNode.next = head; head.next = null; return newHead; } |
个人认为这种解法思路清奇，不太直观，但是依然能解决问题。
（3）比较相似的解题思路
思路和（1）没有什么区别。
ReverseLinkedList.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
public Node reverse3(Node head) { if (head == null || head.next == null) return head; Node pre = null; Node curr = head; while (curr != null) { Node next = curr.next; curr.next = pre; pre = curr; curr = next; } return pre; } |
三、总结
此题算是比较简单，稍微想一想就能得到（1）的解法。参考别人的解题思路反而比较难以理解…