題目:

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 = next
class 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 = next
class 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%)

那我們下題見