---
# System prepended metadata

title: '**Leetcode筆記(Reverse Linked List)**'
tags: [easy, linked list, leetcode]

---

# **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`