反转链表（花式反转）

题目描述

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：

1. 输入：head = [1,2,3,4,5]
2. 输出：[5,4,3,2,1]

复制代码

示例 2：

1. 输入：head = [1,2]
2. 输出：[2,1]

复制代码

示例 3：

1. 输入：head = []
2. 输出：[]

复制代码

提示：
<ul>链表中节点的数目范围是 [0, 5000]
-5000 next 的指向了，将cur->next 指向pre ，此时已经反转了第一个节点了。
接下来，就是循环走如下代码逻辑了，继续移动pre和cur指针。
最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。 此时return pre指针就可以了，pre指针就指向了新的头结点。
</ol>

1. // 双指针
2. class Solution {
3.     public ListNode reverseList(ListNode head) {
4.         if (head == null || head.next == null) {
5.             return head;
6.         }
7.         // 由于单链表的结构，至少要用三个指针才能完成迭代反转
8.         // cur 是当前遍历的节点，pre 是 cur 的前驱结点，temp 是 cur 的后继结点
9.         ListNode prev = null;
10.         ListNode cur = head;
11.         ListNode temp = null;
12.         while (cur != null) {
13.             temp = cur.next;// 保存下一个节点
14.             cur.next = prev;//当前节点指向prev节点
15.             prev = cur;
16.             cur = temp;
17.         }
18.         return prev;
19.     }
20. }

复制代码

上面操作单链表的代码逻辑不复杂，而且也不止这一种正确的写法。但是操作指针的时候，有一些很基本、很简单的小技巧，可以让你写代码的思路更清晰：
需要注意循环的终止条件。要知道循环终止时，各个指针的位置，这样才能保返回正确的答案。如果你觉得有点复杂想不清楚，那就动手画一个最简单的场景跑一下算法，比如这道题就可以画一个只有两个节点的单链表 1->2，然后就能确定循环终止后各个指针的位置了。
递归解法

上面的迭代解法操作指针虽然有些繁琐，但是思路还是比较清晰的。如果现在让你用递归来反转单链表，有没啥想法？对于刚开始刷题的小伙伴来说，可能很难想到，这很正常。如果有解过二叉树系列算法题，回头再来看这道题，就有可能有想法解这道题了。因为二叉树结构本身就是单链表的延伸，相当于是二叉链表嘛，所以二叉树上的递归思维，套用到单链表上是一样的。
递归反转单链表的关键在于，这个问题本身是存在子问题结构的。
例如，现在给你输入一个以 1 为头结点单链表 1->2->3->4，那么如果忽略这个头结点 1，只拿出 2->3->4 这个子链表，它也是个单链表对吧？
那么这个 reverseList 函数，只要输入一个单链表，就能给我反转对吧？那么能不能用这个函数先来反转 2->3->4 这个子链表呢，然后再想办法把 1 接到反转后的 4->3->2 的最后面，是不是就完成了整个链表的反转？
也就是

1. reverseList(1->2->3->4) = reverseList(2->3->4) -> 1

复制代码

这就是「分解问题」的思路，通过递归函数的定义，把原问题分解成若干规模更小、结构相同的子问题，最后通过子问题的答案组装原问题的解。

1. class Solution {
2.     // 定义：输入一个单链表头结点，将该链表反转，返回新的头结点
3.     public ListNode reverseList(ListNode head) {
4.         if (head == null || head.next == null) {
5.             return head;
6.         }
7.         ListNode last = reverseList(head.next);
8.         head.next.next = head;
9.         head.next = null;
10.         return last;
11.     }
12. }

复制代码

对于「分解问题」思路的递归算法，最重要的就是明确递归函数的定义。具体来说，我们的 reverseList 函数定义是这样的：输入一个节点 head，将「以 head 为起点」的链表反转，并返回反转之后的头结点。
明白了函数的定义，再来看这个问题，这段代码似乎就很好理解了
借用栈

借用栈先进后出的能力（或者双端队列，一端进，另一端出也是一样的效果）

• 首先将所有的结点入栈
  
• 然后创建一个虚拟虚拟头结点，让cur指向虚拟头结点。然后开始循环出栈，每出来一个元素，就把它加入到以虚拟头结点为头结点的链表当中，最后返回即可。
  

1. class Solution {  
2.   
3.     public ListNode reverseList(ListNode head) {  
4.         // 如果链表为空，则返回空  
5.         if (head == null) return null;  
6.         // 如果链表中只有只有一个元素，则直接返回  
7.         if (head.next == null) return head;  
8.   
9.         // 声明一个双端队列  
10.         ArrayDeque<ListNode> stack = new ArrayDeque<>();  
11.         ListNode cur = head;  
12.   
13.         while (cur != null) {  
14.             stack.push(cur);  
15.             cur = cur.next;  
16.         }  
17.   
18.         // 创建一个虚拟头结点  
19.         ListNode pHead = new ListNode(0);  
20.         cur = pHead;  
21.         while (!stack.isEmpty()) {  
22.             ListNode node = stack.pop();  
23.             cur.next = node;  
24.             cur = cur.next;  
25.         }  
26.         // 最后一个元素的next要赋值为空  
27.         cur.next = null;  
28.         return pHead.next;  
29.     }  
30. }

复制代码

解法总结

最好的方式还是双指针解法；如果数据量较大，递归解法和借用栈的方式都有可能导致栈溢出的情况

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！