当前位置：首页 > article >正文

python-leetcode 23.反转链表

article 2025/2/12 0:11:36

题目：

给单链表的头节点，反转链表，并返回反转后的链表。

方法一：迭代

在遍历链表时，将当前节点的next指针改为指向前一个节点。由于节点没有引用其前一个节点，因此要先存储前一个节点，在更改引用之前，还要存储后一个节点，最后返回新的头引用。

链表注意：上一个，现在，下一个的关系

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def reverseList(self, head):
        """
        :type head: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        prev=None  #用来追踪上一个节点的指针，初始为空
        curr=head   #当前处理的节点，初始化为链表的头节点
        while curr is not None:
            next_node=curr.next  #当前节点指向的下一个节点
            curr.next=prev  #反转当前节点的指向，让当前节点指向前一个节点
            prev=curr #将前一指针移动到当前节点curr,以便下一个节点反转时，当前节点成为下一个节点的前驱节点
            curr=next_node #指针后移，继续遍历
        return prev

时间复杂度：O(N)

空间复杂度：O(1)

方法二：递归

假设链表为：n1→…→nk−1→nk→nk+1→…→nm→∅

若从节点nk+1到nm已经被反转，而我们处于nk,n1→…→nk−1→nk→nk+1←…←nm

希望nk.next.next=nk

需要注意的是 n1 的下一个节点必须指向 ∅。如果忽略了这一点，链表中可能会产生环。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def reverseList(self, head):
        """
        :type head: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        if head is None or head.next is None:  #链表为空或者链表只有一个节点，返回当前节点
            return head
        newhead=self.reverseList(head.next) #对链表的下一个节点递归调用，直到链表末尾
        head.next.next=head #反转指针，当前节点head设为下一个节点head.next 的下一个节点
        head.next=None  #将当前节点 head 的 next 指针设为 None，避免形成环
        return newhead

时间复杂度：O(N)

空间复杂度：O(N)

查看全文

http://www.kler.cn/a/541326.html