Leetcode # 206. Reverse Linked List

https://leetcode.com/problems/reverse-linked-list/

Solution

Time Complexity: O(n)
Space Complexity: O(1)

Python 版

class Solution:
  def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    cur, pre = head, None
    while cur:
        cur.next, cur, pre = pre, cur.next, cur
    return pre

Order of Multiple Assignment in Python

  1. 先計算等號右側的數值
  2. 依序賦值給等號右側的變數

cur.next, cur, pre = pre, cur.next, cur

  1. 先計算「右側的 pre, cur.next, cur」
     = node_1, node_3, node_2
  2. 賦值 node_1 給「左側的 cur.next 」
    「即 node_2.next 」
  3. 賦值 node_3 給「左側的 cur 」
  4. 賦值 node_2 給「左側的 pre 」

 pre, cur, cur.next = cur, cur.next, pre

  1. 先計算「右側的 cur, cur.next, pre」
     = node_2, node_3, node_1
  2. 賦值 node_2 給「左側的 pre 」
  3. 賦值 node_3 給「左側的 cur 」
  4. 賦值 node_1 給「左側的 cur.next 」
    但是此時的 cur 已經是 node_3
    而非原本的 node_2

C++ 版

class Solution {
public:
  ListNode* reverseList(ListNode* head) {
    ListNode *pre = NULL, *cur = head;
    while(cur){
      ListNode *temp = cur->next;
      cur->next = pre;
      pre = cur;
      cur = temp;
    }
    return pre;
  }
};

 

Last Updated on 2023/08/16 by A1go

目錄

→ 目錄
Bitnami