iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 17
3

這題其實理解了好一陣子,假如有錯誤的地方麻煩幫我指證了


206. Reverse Linked List

// Question:
Reverse a singly linked list.
// Example:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {

}

https://ithelp.ithome.com.tw/upload/images/20190918/20106426xQyGHJzEAF.jpg

Think

極限值/特殊狀況

  • Linked List 裡面沒有 node
  • 只有一個 node (所以反轉後還是它自己)
// 處理極端值
// linked list 裡面沒東西
if(!head){
    return null
}
// 只有一個值所以反轉之後還是他自己
if(!head.next){
    return head;
}

哪種資料結構解

  • Linked List (範例都給你 ListNode 了)

大概會怎麼解

主要就是反轉指標,本來是 prev 的變成 next。

  • 首先會定義三個東西
    • cur: 初始值 = head,然後判斷完會往下一個 node 移動 cur = cur.next
    • temp: 暫存 cur
    • prev: 初始值 = null,這個用來反轉指標
 let prev = null,
    cur = head,
    temp;

https://ithelp.ithome.com.tw/upload/images/20190918/20106426UlaRopbQ8n.jpg

temp = cur;   // 用 temp 來存目前的 node,不然會被後面的操作影響
cur = cur.next;   // 目前的 node 指標先往下
// 將 next 指向先前的值
temp.next = prev; 
// prev 變成先前的值
prev = temp;

然後一直重覆以上步驟,直到結束 (current.next == null 代表結束了)
https://ithelp.ithome.com.tw/upload/images/20190918/20106426uJuKpuKAPU.jpg

https://ithelp.ithome.com.tw/upload/images/20190918/20106426BjDAYEjZU6.jpg

完整程式碼

var reverseList = function(head) {
    // 極端值
    // linked list 裡面沒東西
    if(!head){
        return null
    }
    // 只有一個值所以反轉之後還是他自己
    if(!head.next){
        return head;
    }

    let prev = null,
    cur = head,
    temp;
    
    while(cur != null){
        temp = cur;   // 用 temp 來存目前的 node,不然會被後面的操作影響
        cur = cur.next;   // 目前的 node 指標先往下

        // 將 next 指向先前的值
        temp.next = prev; 

        // prev 變成先前的值
        prev = temp;
    }

    return prev;

};

自己思考 Linked List 時的確花了更多時間來理解,不過學東西本來就這樣嘛,一開始總是辛苦,後來會發現是值得的。有邦友說 Linked List 在 React 底層有用到,雖然我們不太可能去親手打造一個 library,但懂這個資料結構在做甚麼我覺得是蠻重要的,有機會看底層的實作流程吸取大師經驗也能比較上手一些。

如有錯誤或需要改進的地方,拜託跟我說。
我會以最快速度修改,感謝您

上一篇
鏈結串列 Linked List
下一篇
資料結構 Data Structure 總結
系列文
前端工程師用 javaScript 學演算法32

尚未有邦友留言

立即登入留言