LeetCode-206. Reverse Linked List

LeetCode-206. Reverse Linked List

難度: easy

Given the head of a singly linked list, reverse the list, and return the reversed list.

 給你一個單向的鍊表，反轉鍊表，並回傳反轉的鍊表。

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2:

Input: head = [1,2]
Output: [2,1]

Example 3:

Input: head = [1,2]
Output: [2,1]

Constraints:

• The number of nodes in the list is the range [0, 5000].
• -5000 <= Node.val <= 5000

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

解題流程

1. 先看懂題目想描述甚麼情境
2. 開始想像程式運作該經過哪些流程
3. 將經過的流程所需的判斷跟細節列出
4. 實作列出的流程

先看懂題目想描述甚麼情境

這題題目很單純，就是要把單向鍊表反轉。

開始想像程式運作該經過哪些流程

一開始的時候就把curr當成鍊表尾巴
一邊把後方的node搬到curr前方的時候還要注意要搬到鍊表的最前方

將經過的流程所需的判斷跟細節列出

• 先用變數紀錄目前的head (curr)
• 當curr還有next再繼續往下走
• 保存目前node的 next next (tempNextNext)
• 保存目前node的 next (tempNext)
• curr next指向 tempNextNext
• tempNext next指向 head
• head 改為 tempNext

實作列出的流程

typescript

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function reverseList(head: ListNode | null): ListNode | null {
    if(!head) return null;
    if(!head.next) return head;
    let curr = head;
    while(curr.next) {
        const tempNextNext = curr.next.next;
        const tempNext = curr.next;
        curr.next = tempNextNext;
        tempNext.next = head;
        head = tempNext;
    }
    return head;
};

解釋: (這個提交寫法有點歷史，所以當初重新看的時候發現有點太複雜，這裡再把想法解釋清楚)
其實上面的做法想做到的事情是

遍歷條件設成如果curr後方還有node
把curr下一個node放到前面的時候，把下下一個node跟curr接起來
(原)下一個node把next指向curr
再把head改為(原)下一個node

因為每次循環都會把curr的下一個再指向head
之後再把它當作head
直到curr後方沒有node代表已經反轉完鍊表

更好的方法

以下方法是參考線上課程解法寫出
發現其實可以直接定義兩個指針，一個代表反轉的鍊表head (p2)，一個代表目前剩餘的鍊表 (p1)，
p1每次都會先把下一個node存起來 (temp )，再指向p2，之後p2改成p1，這樣下一輪再指向next才可以指到上一個被反轉的node。
最後回傳p2就好，因為其實p2就是p1反轉後的結果。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function reverseList(head: ListNode | null): ListNode | null {
    let p1 = head;
    let p2 = null;

    while(p1) {
        const temp = p1.next;
        p1.next = p2;
        p2 = p1;
        p1 = temp;
    }
    return p2;
};

感謝閱讀，如果有錯誤或是講得不清楚的部分，再請留言指教