206. Reverse Linked List

發表於 分類於 ， 閱讀次數： 文章字數： 833

種類 : linked list
難度 : easy
題目 : 206. Reverse Linked List

思維邏輯

  1. prev: 紀錄舊node.next
  2. tmp: 紀錄當前node

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    """
    雖然ListNode為singly-linked list，但反轉時使用doubly linked list概念
    """
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = head
        tmp = None
        while cur:
            # 紀錄舊node.next
            prev = cur.next
            # 修改node.next
            cur.next = tmp
            # 記錄當前node
            tmp = cur
            # 切換當前node
            cur = prev
        return tmp

時間複雜度: O(n)
空間複雜度: O(1)

難點

  1. 紀錄node與切換node時間點
  2. 迴圈結束規則(當前node是否為None)

最佳解法

1
2
3
4
5
6
7
8
9
10
# 遞歸
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        return self.reverse(head, None)
    def reverse(self, cur: ListNode, pre: ListNode) -> ListNode:
        if cur == None:
            return pre
        temp = cur.next
        cur.next = pre
        return self.reverse(temp, cur)

時間複雜度: O(n)
空間複雜度: O(n)，調用n層