206 反转链表
2022/9/1 23:26:06
本文主要是介绍206 反转链表,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目206 反转链表
给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
示例 1:
输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]
示例 2:
输入:head = [1,2]
输出:[2,1]
示例 3:
输入:head = []
输出:[]
双指针思路:
- 定义指针cur指向head,定义指针pre,定义为None,作为链表的最后节点的指向节点
- 然后开始反转了,定义一个临时指针temp保存cur.next节点,因为反转后cur指针的next指向pre,不在是原先的cur.next节点了,将cur->next 指向pre,此时已经反转了第一个节点了。
- 接下来,就是循环走如下代码逻辑了,继续移动pre和cur指针。
- 最后,cur 指针已经指向了null,循环结束,链表也反转完毕了。 此时我们return pre指针就可以了,pre指针就指向了新的头结点。
注意:本来考虑head和head.next是否为空,最后发现为空也不影响结果。
代码
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: # if head != None and head.next != None: # pre = None # cur = head # while cur != None: # temp = cur.next # cur.next = pre # pre = cur # cur = temp # return pre # return head pre = None cur = head while cur != None: temp = cur.next cur.next = pre pre = cur cur = temp return pre
递归思路
建议双指针思路,递归直接不容易写,但是根据双指针代码,可以写出递归代码。
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: # pre = None # cur = head # while cur != None: # temp = cur.next # cur.next = pre # pre = cur # cur = temp # return pre return self.reverse(None, head) def reverse(self, pre, cur): while cur != None: temp = cur.next cur.next = pre return self.reverse(cur, temp) return pre
这篇关于206 反转链表的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-08阿里云域名注册流程,分享给第一次购买域名的新手站长!
- 2024-05-082024年,行业变动下的程序员应该首先学习哪种编程语言?
- 2024-05-08我在下载模块的时候下不下来出现这种情况是什么意思?
- 2024-05-08最近很火的低代码到底是什么?
- 2024-05-08设计模式Java实现-建造者模式
- 2024-05-08设计模式Java实现-原型模式
- 2024-05-08记一次java进程频繁挂掉问题排查修复
- 2024-05-08test
- 2024-05-0802-大厂电商设计解析之商品管理系统
- 2024-05-08迭代的难题:敏捷团队每次都有未完成的工作,如何破解?