# **Leetcode筆記(Reverse Linked List)** :::info :information_source: 題目 : Reverse Linked List, 類型 : linked list , 等級 : easy 日期 : 2023/02/25，2023/05/30，2023/12/03，2024/09/01 ::: ### 嘗試 從dp戰場換到這邊，一下子就過了，果然初學者還是要循序漸進的練... 時間複雜度O(n)，空間複雜度O(1) ```python # 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]: previous = None current = head while current != None: tmp = current current = current.next tmp.next = previous previous = tmp head = previous return head ``` 2023/05/30，看到上面的留言，希望給自己一個加油 ```python class Solution: def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: pre = None cur = head while cur: temp = cur.next cur.next = pre pre = cur cur = temp return pre # 最後cur會是None，pre是倒反的head，所以不是回傳cur.next ``` 2023/07/01，有點忘記linked list的實作方式 ```python # 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]: pre, cur = None, head while cur: tmp = cur.next cur.next = pre pre = cur cur = tmp return pre ``` 2023/12/03 ```python class Solution: def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: pre, cur = None, head while cur: temp = cur.next cur.next = pre pre = cur cur = temp return pre ``` 2024/09/01 ```python class Solution: def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: pre = None while head: tmp = head.next head.next = pre pre = head head = tmp return pre ``` --- ### **優化** 步驟，先用一個tmp紀錄current下一個數字(current.next) current的指標可以反轉回去了(指向previous) previous更新到下一個(變current) current更新到下一個(變current再下一個)(也就是tmp) 時間複雜度O(n)，空間複雜度O(1) ```python # 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]: previous = None current = head while current != None: tmp = current.next current.next = previous previous = current current = tmp head = previous return head ``` --- **:warning: 錯誤語法** :::warning python中沒有null，只有None ::: **:thumbsup:學習** :::success ::: **思路** ![](https://i.imgur.com/BB5X0Qe.png) **講解連結** https://www.youtube.com/watch?v=G0_I-ZF0S38 https://hackmd.io/@Hsins/in-place-reversal-of-linked-List Provided by. NeetCode ###### tags: `linked list` `easy` `leetcode`