Leetcode 206. 反转链表
题目描述
反转一个单链表。
示例 1:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
迭代解法
遍历链表，以 cur 表示当前节点，以 last 表示上一个节点，将 cur 的 next 指针指向 last 即可。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
last,cur=None,head
while cur:
cur.next,cur,last=last,cur.next,cur
return last这里使用了 python 的多元赋值，等号右边的值在赋值操作结束前会保持不变。
递归解法
以 reverseList(node) 函数表示 node 节点为头结点的反转链表，则 reverseList(node) 的反转链表为 reverseList(node.next) 尾部追加 node 节点，即 node.next.next = node。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
ret=self.reverseList(head.next)
head.next.next,head.next=head,None
return ret在执行 node.next.next = node 后，设置 node.next = None，避免最后两个节点形成循环。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019.06.04 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读