力扣-反转链表

力扣-反转链表

转自 leetcode

https://leetcode-cn.com/problems/reverse-linked-list/solution/dong-hua-yan-shi-206-fan-zhuan-lian-biao-by-user74/

leetcode 206 反转链表

利用外部空间

这种方式很简单,先申请一个动态扩容的数组或者容器,比如 ArrayList 这样的。
然后不断遍历链表,将链表中的元素添加到这个容器中。
再利用容器自身的 API,反转整个容器,这样就达到反转的效果了。
最后同时遍历容器和链表,将链表中的值改为容器中的值。
因为此时容器的值是:

5 4 3 2 1

链表按这个顺序重新被设置一边,就达到要求啦。
当然你可以可以再新创建 N 个节点,然后再返回,这样也可以达到目的。
这种方式很简单,但你在面试中这么做的话,面试官 100% 会追问是否有更优的方式,比如不用外部空间。所以我就不做代码和动画演示了,下面来看看如何用 O(1)O(1) 空间复杂度来实现这道题。

双指针迭代

我们可以申请两个指针,第一个指针叫 pre,最初是指向 null 的。
第二个指针 cur 指向 head,然后不断遍历 cur。
每次迭代到 cur,都将 cur 的 next 指向 pre,然后 pre 和 cur 前进一位。
都迭代完了(cur 变成 null 了),pre 就是最后一个节点了。
动画演示如下:

力扣-反转链表
Java:
class Solution {
	public ListNode reverseList(ListNode head) {
		//申请节点,pre和 cur,pre指向null
		ListNode pre = null;
		ListNode cur = head;
		ListNode tmp = null;
		while(cur!=null) {
			//记录当前节点的下一个节点
			tmp = cur.next;
			//然后将当前节点指向pre
			cur.next = pre;
			//pre和cur节点都前进一位
			pre = cur;
			cur = tmp;
		}
		return pre;
	}
}

递归解法

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

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

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

力扣-反转链表
Java:
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;
	}
}

链表相关文章汇总

题号题目题解难度等级
19删除链表的倒数第N个节点两种实现+图解中等
21合并两个有序链表两种实现+图解简单
23合并K个升序链表四种实现+图解困难
24两两交换链表中的节点三种实现+图解中等
25K 个一组翻转链表两种实现+图解困难
61旋转链表两种实现+图解中等
82删除排序链表中的重复元素 II三种实现+图解中等
83删除排序链表中的重复元素两种实现+图解简单
141二叉树展开为链表四种实现+图解中等
138复制带随机指针的链表两种实现+图解中等
141环形链表两种实现+图解简单
160相交链表两种实现+图解简单
203移除链表元素两种实现+图解简单
206反转链表两种实现+图解简单
234回文链表图解简单
237删除链表中的节点图解简单
876链表的中间结点图解简单

给TA打赏
共{{data.count}}人
人已打赏
计算机基础

岛屿类问题的通用解法、DFS 遍历框架

2021-7-18 14:29:57

计算机基础

C++11 之右值引用、移动语义和完美转发

2021-9-16 10:32:33

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索