leetcode with python:206. Reverse Linked List

题目:

Given the head of a singly linked list, reverse the list, and return the reversed list.

给定一个linked list,将其反转回传

一开始我是直观用迭代的方式去解

# Definition for singly-linked list.# class ListNode:#     def __init__(self, val=0, next=None):#         self.val = val#         self.next = nextclass Solution:    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:        if not head: #防一开始head是None            return None                    pre=None        while head:            temp=head            head=head.next            temp.next=pre            pre=temp        return pre

一开始存前一Node的变数(pre)设None
之后开始循环:
暂存值(temp)存下head=>head前往head.next=>藉由temp将head.next改为pre=>pre变为temp(即head)=>回第一步
一次循环就反转了一个node,我们就不断迭代直到head跑到None
此时的pre为新linked list的头(此时在None的head的上一个Node),回传它即可
最后执行时间37ms(faster than 92.61%)

另外分享一个在讨论区看到的递迴解
虽然我自己也有写一个递迴解但远不如这个解巧妙

# Definition for singly-linked list.# class ListNode:#     def __init__(self, val=0, next=None):#         self.val = val#         self.next = nextclass Solution:    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:        if not head: #一开始head就是None则回传None            return None                    newhead=head        if head.next:            newhead=self.reverseList(head.next)            head.next.next=head        head.next=None        return newhead

首先我们要先找到linked list的尾端,再从尾端开始做反转的动作
所以当head.next不为None时,我们不断往下寻找
当抵达末端时(同时将其记录为newhead)我们就可以开始反转的工程了
末端我们不做处理,我们以倒数第二项为範例:

将其下一个node(末项)的下一个node变为自己(这样末项就指向倒数第二项了)
再将自己的next变为None,这样我们就完成倒数两项的反转linked list了
倒数第三项同理
将其下一个node(倒数第二项)的下一个node变为自己(这样倒数第二项就指向倒数第三项了)
再将自己的next变为None,这样我们就完成倒数三项的反转linked list了
如此重複

不管第几次我们回传的都是newhead(即末项,也就是反转linked list的头)
这样我们最后一次操作后回传newhead,同时我们也完成了linked list的反转
最后执行时间30ms(faster than 98.94%)

那我们下题见