JZTXT

leetCode 206 反转链表（头插法+ 两种递归）

发布时间 2023-04-19 11:27:02作者: Serein_MK

递归

  1. # 优先处理尾部的链表，此时需要返回子链表的头节点和尾节点
# 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:
            head, _ = self.func(head)
        return head

    def func(self, head):
        if not head.next:
            return head, head
        cur = head
        sonh, sont = self.func(cur.next)
        sont.next, cur.next = cur, None
        return sonh, cur


  2. # 优先处理头部链表，此时参数中需要指明前节点pre和当前节点p
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        return self.func(None, head)

    def func(self, pre, p):
        if not p:
            return pre
        nxt, p.next = p.next, pre
        return self.func(p, nxt)

迭代

  1. # 采用头插法, 多元赋值时会先把右边的计算出来，然后再进行赋值

# 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]:
        dmyn = ListNode()
        dmyn.next, p = head, head
        while p and p.next:
            p.next.next, dmyn.next, p.next = dmyn.next, p.next, p.next.next

        
        return dmyn.next