使用 javascript / python

iteration / recursion

 

iteration

這題使用 while 相對直覺，網上很多解說影片找個聽得懂的看得懂的多看幾遍就有感覺了...(應該)

交換的重點在於將「指向下一個 head.next」改成指向「前一個節點 prev」

 

這篇動畫蠻棒的...

LeetCode 雙刀流：206. Reverse Linked List

 

var reverseList = function(head) {
    if (head === null) return head;
    let curr = head;
    let reverse = null;
    while (curr) {
      let tmp = curr.next;
      curr.next = reverse;
      reverse = curr;
      curr = tmp;
    }
    return reverse;
};

 

用文字來粗暴直觀的感受一下反轉 ABCDE:

 

curr	tmp=curr.next	curr.next = reverse	reverse=curr	curr=tmp
A	B	null	A	B
B	C	A	BA	C
C	D	BA	CBA	D
D	E	CBA	DCBA	E
E	null	DCBA	EDCBA	null

 

想一下應該就懂了，還不懂就想兩下（Ｘ

recursion 

卡住很久...

 

var reverseList = function(head) {
    if (head === null || head.next === null) {
        return head;
    }
    // 如果 head.next === null 表示這是目前 linked list 的最後一個 node
    let reversedHead = reverseList(head.next);

    head.next.next = head;
    head.next = null;

    return reversedHead;
};

 

影片圖解

Reverse a Linked List Recursively

 

這個影片 6:36 開始用上色說明，蠻清楚的，茅塞頓開

Software interview question - Reverse a linked list recursively

 

head.next.next = head;
9:30 有說到這行邏輯，他兩個箭頭方向是不同的!!

 

同樣以 ABCDE 為例，當 head = D，reversedHead 會得到 E

A > B > C > D > E > null

要反轉這個 linkedlist ，需要做的是在找到最後一個 node 的時候，讓它指回去它的前一個 node

所以，head = D 時，已知 head.next = E 是最後一個 node，

怎麼讓 E 指回去呢? 那就 head.next.next = head！！！！！！！

變成這樣

A > B > C > D > E > null

A > B > C > D <

與此同時還要配合下一行的

head.next = null

然後返回 reversedHead 。

 
 

python 是寫好 javascript 再改，主要是作為熟悉語法的練習。

 

# 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 head is None:
            return head
        curr = head
        reverse = None
        while curr:
            tmp = curr.next
            curr.next = reverse
            reverse = curr
            curr = tmp
        return reverse

 

# 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 head is None or head.next is None:
            return head
        
        reverseHead = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return reverseHead

 

速度上 javascript < python iteration < python recursion

我也不懂為什麼XD