余瑜的博客 余瑜的博客
首页
  • 并发
  • 线程池
  • spring
  • maven
  • 其他
  • redis
  • mysql
  • linux
  • zookeeper
  • docker
  • terminal
  • kong插件开发
  • 资料
  • leetCode-简单
  • blog
  • 其他
关于
GitHub (opens new window)
首页
  • 并发
  • 线程池
  • spring
  • maven
  • 其他
  • redis
  • mysql
  • linux
  • zookeeper
  • docker
  • terminal
  • kong插件开发
  • 资料
  • leetCode-简单
  • blog
  • 其他
关于
GitHub (opens new window)
  • 资料

  • leetCode-简单

    • 两数之和
    • 整数反转
    • 回文数
    • 罗马数字转整数
    • 反转链表
    • 堆栈和队列互相模拟
  • 算法
  • leetCode-简单
余瑜
2021-08-31

反转链表

递归解法 这题有个很骚气的递归解法,递归解法很不好理解,这里最好配合代码和动画一起理解。 递归的两个条件:

终止条件是当前节点或者下一个节点==null 在函数内部,改变节点的指向,也就是 head 的下一个节点指向 head 递归函数那句

head.next.next = head 很不好理解,其实就是 head 的下一个节点指向head。 递归函数中每次返回的 cur 其实只最后一个节点,在递归函数内部,改变的是当前节点的指向。 动画演示如下:

递归.gif

class Solution {
	public ListNode reverseList(ListNode head) {
		//递归终止条件是当前为空,或者下一个节点为空
		if(head==null || head.next==null) {
			return head;
		}
		//这里的cur就是最后一个节点
		ListNode cur = reverseList(head.next);
		//这里请配合动画演示理解
		//如果链表是 1->2->3->4->5,那么此时的cur就是5
		//而head是4,head的下一个是5,下下一个是空
		//所以head.next.next 就是5->4
		head.next.next = head;
		//防止链表循环,需要将head.next设置为空
		head.next = null;
		//每层递归函数都返回cur,也就是最后一个节点
		return cur;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

作者:wang_ni_ma 链接:https://leetcode-cn.com/problems/reverse-linked-list/solution/dong-hua-yan-shi-206-fan-zhuan-lian-biao-by-user74/ 来源:力扣(LeetCode)

上次更新: 2021/10/22, 16:08:06

← 罗马数字转整数 堆栈和队列互相模拟→

Theme by Vdoing | Copyright © 2018-2022 逆光世间 | 备案号: 京ICP备19016086号
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式