leetcode206-反转链表
2021/8/3 23:08:33
本文主要是介绍leetcode206-反转链表,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
一.题目描述
给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]
输入:head = [1,2]
输出:[2,1]
输入:head = []
输出:[]
提示:
链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000
二.题目解析
1.递归法
public ListNode reverseList1(ListNode head) { /*递归方式,递推公式reverseList的含义是:把拿到的链表进行反转,然后返回新的头结点。 * */ //判断链表为空或者只有一个元素 || 递归终止条件 if(head == null || head.next == null){ return head; } //返回当前元素后面所有节点反转后的头结点(是固定的) ListNode leftHead = reverseList(head.next); //2 --> 3<--4 => 2.next.next = 2 即实现了反转 head.next.next = head; //head置为空返回到上一层递归调用会被重新赋值(head.next.next = head) head.next = null; //每层调用返回的leftHead是一样的 return leftHead; }
2.双指针迭代遍历
public ListNode reverseList(ListNode head) { /*迭代方式 * */ //判断链表为空或者只有一个元素 if(head == null || head.next == null){ return head; } ListNode pre = head; ListNode cur = head.next; ListNode nextPre = new ListNode(); ListNode nextCur = new ListNode(); while(cur != null){ //由于后边cur指向会发生变化,先备份nextPre和nextCur nextCur = cur.next; cur.next = pre; if(pre == head){ pre.next = null; } //更新指针 pre = cur; cur = nextCur; } //最终的pre指向就是反转后的头结点 return pre; }
这里还可以优化一下,不需要单独考虑头结点
令pre初始值为null,cur初始值是头结点即可
public ListNode reverseList(ListNode head) { /*迭代方式 * */ //判断链表为空或者只有一个元素 if(head == null || head.next == null){ return head; } ListNode pre = null; ListNode cur = head; ListNode nextPre = new ListNode(); ListNode nextCur = new ListNode(); while(cur != null){ //由于后边cur指向会发生变化,先备份nextCur nextCur = cur.next; cur.next = pre; //更新指针 pre = cur; cur = nextCur; } //最终的pre指向就是反转后的头结点 return pre; }
这篇关于leetcode206-反转链表的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-30uniAPP 实现全屏左右滚动滚动的效果-icode9专业技术文章分享
- 2024-06-30如何在本地使用授权或插件-icode9专业技术文章分享
- 2024-06-30伪静态规则配置方法汇总-icode9专业技术文章分享
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享
- 2024-06-28忘记eyoucms后台密码怎么办?-icode9专业技术文章分享
- 2024-06-26终极指南:Scrum中如何设置需求优先级
- 2024-06-26AI大模型企业应用实战(25)-为Langchain Agent添加记忆功能
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding