LeetCode 206. 反转链表
215 views
0
LeetCode：https://leetcode-cn.com/problems/reverse-linked-list/
题目描述：反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
解法1： 借助中间节点变量，分割成两个链表(结果链表、遍历链表)，依次反转链表节点
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
// 循环移动，拼接当前节点，反转链表
public ListNode reverseList(ListNode head) {
ListNode result = null;
ListNode curr = head;
while(curr != null) {
ListNode next = curr.next; // 1. 先保存当前节点的下一个节点(保存现场)
curr.next = result; // 2. 当前节点指向结果链表的头节点
result = curr; // 3. 结果的头结点左移, 指向当前节点
curr = next; // 4. 当前节点指向保存的下一个节点
}
return result; // 返回结果链表的头结点
}
}
若想分析具体过程，可以打印出链表反转的日志，如下：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public void printList(String tag, int count, ListNode result, ListNode curr) {
System.out.printf("\n %s --- count=%d +++ result: ", tag, count);
while(result != null) {
System.out.printf("%d->", result.val);
result = result.next;
}
System.out.printf("null");
System.out.printf(" +++ curr: ");
while(curr != null) {
System.out.printf("%d->", curr.val);
curr = curr.next;
}
System.out.printf("null");
}
public ListNode reverseList(ListNode head) {
ListNode result = null;
ListNode curr = head;
// 1->2->3->4->5->NULL
// 1->NULL 2->3->4->5->NULL
// 2->1->NULL 3->4->5->NULL
// 3->2->1->NULL 4->5->NULL
// 4->3->2->1->NULL 5->NULL
// 5->4->3->2->1->NULL NULL
int count = 0;
while(curr != null) {
ListNode next = curr.next; // 2
curr.next = result; // null
result = curr; // 1
curr = next; // 2
printList("reverseList", count, result, curr);
count++;
}
return result;
}
}
说明：
1）输入 [1,2,3,4,5]
2）输出 [5,4,3,2,1]
3）预期结果 [5,4,3,2,1]
打印出的日志结果：
reverseList --- count=0 +++ result: 1->null +++ curr: 2->3->4->5->null reverseList --- count=1 +++ result: 2->1->null +++ curr: 3->4->5->null reverseList --- count=2 +++ result: 3->2->1->null +++ curr: 4->5->null reverseList --- count=3 +++ result: 4->3->2->1->null +++ curr: 5->null reverseList --- count=4 +++ result: 5->4->3->2->1->null +++ curr: null
解法2： 借助栈Stack()来求解, 简单直观
但这可能不符合此题本意（不要用任何数据结构, 队列栈容器等）
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
// 借助栈Stack()来求解, 简单直观, 但可能不符合此题本意（不要用任何数据结构, 队列栈容器等）
public ListNode reverseList(ListNode head) {
ListNode result = new ListNode(); // 结果头结点
ListNode curr = result;
// 1. 压栈, 使用了额外的数据结构Stack()和存储空间, 不是最优解
Stack<ListNode> stack = new Stack<ListNode>();
while(head != null) {
stack.push(head);
head = head.next;
}
// 2. 出栈, 拼接成链表
while(stack.size() > 0) {
ListNode node = stack.pop();
curr.next = node;
curr = node;
}
curr.next = null; // 设置为节点结束符null, 因为Stack()出栈后实际是一个循环链表 5->4->3->2->1->2->1->2....
return result.next;
}
}
解法3： 递归实现，特别注意边界的停止条件、边界的细节（头结点要设置为null，不要有循环链表、环链表）
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
// 递归实现
public ListNode reverseList(ListNode head) {
// 第一行代码判断, 两层含义:
// 1. head == null, head为空链表, 直接返回 head = null
// 2. head.next == null, head是最后一个节点, 直接返回最后节点
if(head == null || head.next == null) {
return head;
}
// 测试用例: 1->2->3->4->5->null
// head不为空, 从第二个节点开始压栈, 此时 head.next = 2
ListNode result = reverseList(head.next);
// 递归压栈后出栈结果 result = 5->4->3->2 没有1->2->null
// 因此继续加上 2->1->null
head.next.next = head; // 这是一个循环链表 1->2->1 两个节点的循环链表
head.next = null; // 设置null, 打断循环链表, 即 1->null
return result; // 最终结果链表 5->4->3->2->1->null
}
}
若想分析递归的具体过程，可以打印出链表反转的日志，如下：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
// 打印链表日志
public void printList(String tag, int count, ListNode result, ListNode curr) {
System.out.printf("\n %s --- count=%d +++ result: ", tag, count);
while(result != null) {
System.out.printf("%d->", result.val);
result = result.next;
}
System.out.printf("null");
System.out.printf(" +++ curr: ");
while(curr != null) {
System.out.printf("%d->", curr.val);
curr = curr.next;
}
System.out.printf("null");
}
// 递归实现, 打印递归的详细步骤
int count = 0; // 计数器, 仅调试用
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null) {
return head; // 边界条件, 返回压入的节点(ListNode)
}
// 输入: 1->2->3->4->5->NULL
// 压栈: 1 2 3 4 5(递归栈顶, 后进先出)
count++;
printList("before", count, null, head);
ListNode result = reverseList(head.next); // 5->4->3->2
printList("after", count, result, head);
// 上面递归压栈的第一个节点是2 即reverseList(head.next), 这里head.next = 2(注意边界)
// 递归压栈全部弹出后的链表结构为: result=5->4->3->2 1->2->null
// 此时, head=1, head.next=2
// 继续赋值 head.next.next=head, 即 2->1 ; head.next=null, 即 2->1->null
// 最终 result = 5->4->3->2->1->null
head.next.next = head; // 结果 head = 1->2->1 是一个循环链表了
head.next = null; // 结果 head = 1->2->1->null 设置null结束符, 打断循环链表, 防止循环, 即 1->null
printList("result", count, result, head);
// 最后, result一直都指向递归栈顶5, 即 5->4->3->2 （截取了head中的2->1->null）
return result;
}
}
说明：
1）输入 [1,2,3,4,5]
2）输出 [5,4,3,2,1]
3）预期结果 [5,4,3,2,1]
打印出的日志结果：
before --- count=1 +++ result: null +++ curr: 1->2->3->4->5->null before --- count=2 +++ result: null +++ curr: 2->3->4->5->null before --- count=3 +++ result: null +++ curr: 3->4->5->null before --- count=4 +++ result: null +++ curr: 4->5->null after --- count=4 +++ result: 5->null +++ curr: 4->5->null result --- count=4 +++ result: 5->4->null +++ curr: 4->null after --- count=4 +++ result: 5->4->null +++ curr: 3->4->null result --- count=4 +++ result: 5->4->3->null +++ curr: 3->null after --- count=4 +++ result: 5->4->3->null +++ curr: 2->3->null result --- count=4 +++ result: 5->4->3->2->null +++ curr: 2->null after --- count=4 +++ result: 5->4->3->2->null +++ curr: 1->2->null result --- count=4 +++ result: 5->4->3->2->1->null +++ curr: 1->null
解法4： 改进递归的方式，采用尾递归来实现，减少额外空间的开销
关于尾递归的概念，请见本文末的"尾递归"介绍
尾递归方式1：采用一个全局变量，始终保存指向前一个链表的头节点
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
// 测试用例 1->2->3->4->5->null
// 第一次递归循环 pre = head = 1->null , next = 2->3->4->5->null
// 第二次递归循环 pre = head = 2->1->null , next = 3->4->5->null
// 继续手动分析。。。
// 第N次递归结束 pre = head = 5->4->3->2->1->null , next = null
ListNode pre = null; // 全局变量, 始终指向前一个链表的头节点
public ListNode reverseList(ListNode head) {
if (head == null ) return head;
// 1->2->3->4->5->null 结束边界为 5
if (head.next == null) {
head.next = pre; // 5->null
return head; // 终止条件 5->4->3->2->1->null, 直接返回反转的链表
}
ListNode next = head.next; // 保存下一个节点(保存现场) next = 2
head.next = pre; // 当前节点指向前一个(左侧)节点 head = 1->null
pre = head; // 移动到当前节点, pre = head = 1->null
return reverseList(next);
}
}
尾递归方式2：改进尾递归，把全局变量节点，放进尾递归的第二个函数参数里保存 （推荐）
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
return reverse(null, head);
}
// 尾递归
// 测试用例 1->2->3->4->5->null
// 初始参数 pre = null, curr = 1->2->3->4->5->null
// 第一次递归循环 pre = 1->null , next = 2->3->4->5->null
// 第二次递归循环 pre = 2->1->null , next = 3->4->5->null
// 继续手动分析。。。
// 第N次递归结束 pre = 5->4->3->2->1->null , next = null
// pre 保存最终的反转结果链表头结点, 也即是尾递归的保存结果参数
public ListNode reverse(ListNode pre, ListNode curr){
if(curr == null) return pre; // 终止递归条件 curr = null
ListNode next = curr.next; // 保存下一个节点现场
curr.next = pre; // 当前节点前一个(左侧)节点
return reverse(curr, next); // curr =
}
}
若想分析尾递归的具体过程，可以打印出链表反转的日志，如下：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
// 打印链表日志
public void printList(String tag, int count, ListNode result, ListNode curr) {
System.out.printf("\n %s --- count=%d +++ result: ", tag, count);
while(result != null) {
System.out.printf("%d->", result.val);
result = result.next;
}
System.out.printf("null");
System.out.printf(" +++ curr: ");
while(curr != null) {
System.out.printf("%d->", curr.val);
curr = curr.next;
}
System.out.printf("null");
}
// 主函数
public ListNode reverseList(ListNode head) {
return reverse(null, head);
}
// 尾递归
// 测试用例 1->2->3->4->5->null
// 初始参数 pre = null, curr = 1->2->3->4->5->null
// 第一次递归循环 pre = 1->null , next = 2->3->4->5->null
// 第二次递归循环 pre = 2->1->null , next = 3->4->5->null
// 继续手动分析。。。
// 第N次递归结束 pre = 5->4->3->2->1->null , next = null
// pre 保存最终的反转结果链表头结点, 也即是尾递归的保存结果参数
int count = 0;
public ListNode reverse(ListNode pre, ListNode curr){
if(curr == null) return pre; // 终止递归条件 curr = null
ListNode next = curr.next; // 保存下一个节点现场
curr.next = pre; // 当前节点前一个(左侧)节点
count++;
printList("reverse", count, pre, curr);
return reverse(curr, next); // curr = pre = 5->4->3->2->1->null
}
}
说明：
1）输入 [1,2,3,4,5]
2）输出 [5,4,3,2,1]
3）预期结果 [5,4,3,2,1]
打印出的日志结果：
reverse --- count=1 +++ result: null +++ curr: 1->null reverse --- count=2 +++ result: 1->null +++ curr: 2->1->null reverse --- count=3 +++ result: 2->1->null +++ curr: 3->2->1->null reverse --- count=4 +++ result: 3->2->1->null +++ curr: 4->3->2->1->null reverse --- count=5 +++ result: 4->3->2->1->null +++ curr: 5->4->3->2->1->null
如果一个函数中所有递归形式的调用都出现在函数的末尾，我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作，这个特性很重要，因为大多数现代的编译器会利用这种特点自动生成优化的代码。
例如：
int facttail(int n, int a)
{
if (n < 0)
return 0;
else if (n == 0)
return 1;
else if (n == 1)
return a;
else
return facttail(n - 1, n * a);
}
当编译器检测到一个函数调用是尾递归的时候，它就覆盖当前的活动记录而不是在栈中去创建一个新的。编译器可以做到这点，因为递归调用是当前活跃期内最后一条待执行的语句，于是当这个调用返回时栈帧中并没有其他事情可做，因此也就没有保存栈帧的必要了。通过覆盖当前的栈帧而不是在其之上重新添加一个，这样所使用的栈空间就大大缩减了，这使得实际的运行效率会变得更高。
在函数式语言Erlang中（亦是栈语言），如果想要保持语言的高并发特性，就必须用尾递归来替代传统的递归。
尾递归的示例
// 线性递归:
long Rescuvie(long n) {
return (n == 1) ? 1 : n * Rescuvie(n - 1);
}
// 尾递归:
long TailRescuvie(long n, long a) {
return (n == 1) ? a : TailRescuvie(n - 1, a * n);
}
// 对比分析
当n = 5时
对于线性递归, 他的递归过程如下:
Rescuvie(5)
{5 * Rescuvie(4)}
{5 * {4 * Rescuvie(3)}}
{5 * {4 * {3 * Rescuvie(2)}}}
{5 * {4 * {3 * {2 * Rescuvie(1)}}}}
{5 * {4 * {3 * {2 * 1}}}}
{5 * {4 * {3 * 2}}}
{5 * {4 * 6}}
{5 * 24}
120
对于尾递归, 他的递归过程如下:
TailRescuvie(5)
TailRescuvie(5, 1)
TailRescuvie(4, 5)
TailRescuvie(3, 20)
TailRescuvie(2, 60)
TailRescuvie(1, 120)
120
小结
很容易看出, 普通的线性递归比尾递归更加消耗资源
在实现上说, 每次重复的过程调用都使得调用链条不断加长
系统不得不使用栈进行数据保存和恢复
而尾递归就不存在这样的问题, 因为他的状态完全由n和a保存
关于尾递归，请参见：什么是尾递归 （知乎）
参考推荐：
LeetCode 543. 二叉树的直径 (任意两结点最长距离)
LeetCode 2. 两链表整数相加生成一个和的新链表（含变异改进算法）
Python 常用加密算法 base64, md5, sha1
版权所有: 本文系米扑博客原创、转载、摘录，或修订后发表，最后更新于 2021-02-19 12:21:15
侵权处理: 本个人博客，不盈利，若侵犯了您的作品权，请联系博主删除，莫恶意，索钱财，感谢！