[筆記] AlphaCamp 不只是刷題的 Leetcode 訓練營

章節連結

課程相關資訊
內容

Linked List
Linked List 邏輯

LeetCode 題目

143. Reorder List
148. Sort List
206. Reverse Linked List

一腳踏入軟體工程師寫 Code 的世界，不免俗地會碰上 Leetcode 的測驗，來測試你的溝通力、系統性地解決問題的能力和如何化抽象為具體。第四週的活動要進入較為難想像的 Linked List 為主。

課程對應章節：Week4 U29~U31

請注意：本系列文章為個人對應課程的消化吸收後，所整理出來的內容。換言之，並不一定會包含全部的課程內容，也有可能會添加其他資源來說明。

內容

Linked List

1. Linked List 屬於較為高階的資料結構，所以多半是需要親自實作
2. 由 Node 組成，並具有指向性連到下一個 Node
3. 實務上，可以分為 Simple Linked List ( 單向 )、Doubly Linked List ( 雙向 )、Circular Linked List ( 環型 )
4. 和 Array 相比，它不需要連續的記憶體空間，資料插入和刪除很方便，但要查找就會辛苦一些
5. Tree 就如同非線性的 Linked List，延展性比起單線的 Linked List 佳

Linked List 邏輯

1. 反轉：在反轉前，要先記下原先的連結狀態，再將連結斷開。通常會搭配 While、遞迴等方法來實作。
2. 若使用遞迴方式解，會利用函式 Stack 的特性，快速將目標元素導引到倒數第二個，並將 cur.next.next 指向自己，將 cur.next 切斷。

LeetCode 題目

143. Reorder List

連結：https://leetcode.com/problems/reorder-list/

var reorderList = function(head) {
    if (!head || !head.next) return head
    // 分快慢指針，用來區分兩邊
    let slow = head
    let fast = head.next
    
    while(fast&&fast.next){
        slow = slow.next
        fast = fast.next.next
    }
    // 分成兩邊後，將右半給反轉，並用將原始 head 的 連結給切斷
    const right = reverseList(slow.next)
    slow.next = null
    merge(head, right)
};

function reverseList(head){
    if(!head) return null
    if(!head.next) return head
    
    let pre = head
    let cur = head.next
    let temp = null
    
    pre.next = null
    
    while(cur !== null){
        temp = cur
        cur = cur.next
        temp.next = pre
        pre = temp
    }
    
    return pre
}

function merge(l1,l2){
    while(l1){
        // 因為是左右左右交互合併，所以要在有 l1 的狀況下進行
        // 保留下原始的 l1, l2 的 next 後的狀態
        // l2 是有可能會沒有 next 的，所以要判斷一下
        let rawL1 = l1.next
        let rawL2 = l2? l2.next : null
        
        l1.next = l2
        
        // 當 l1.next 接到 null，代表 l2 沒有了，可以跳出
        if(l1.next === null){
            break
        }
        
        l2.next = rawL1
        l1 = rawL1
        l2 = rawL2
    }
}

var reorderList = function(head) {

if (!head || !head.next) return head

// 分快慢指針，用來區分兩邊

let slow = head

let fast = head.next

while(fast&&fast.next){

slow = slow.next

fast = fast.next.next

}

// 分成兩邊後，將右半給反轉，並用將原始 head 的連結給切斷

const right = reverseList(slow.next)

slow.next = null

merge(head, right)

};

function reverseList(head){

if(!head) return null

if(!head.next) return head

let pre = head

let cur = head.next

let temp = null

pre.next = null

while(cur !== null){

temp = cur

cur = cur.next

temp.next = pre

pre = temp

}

return pre

}

function merge(l1,l2){

while(l1){

// 因為是左右左右交互合併，所以要在有 l1 的狀況下進行

// 保留下原始的 l1, l2 的 next 後的狀態

// l2 是有可能會沒有 next 的，所以要判斷一下

let rawL1 = l1.next

let rawL2 = l2? l2.next : null

l1.next = l2

// 當 l1.next 接到 null，代表 l2 沒有了，可以跳出

if(l1.next === null){

break

}

l2.next = rawL1

l1 = rawL1

l2 = rawL2

}

148. Sort List

連結：https://leetcode.com/problems/sort-list/

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
var sortList = function(head) {
    if(!head || !head.next) return head
    let slow = head
    let fast = head.next
    
    while(fast && fast.next){
        slow = slow.next
        fast = fast.next.next
    }
    
    const right = slow.next // 定義右半
    slow.next = null // 將原始的 head 和右半切斷
    
    // 反覆堆疊 sortList 的結果後，並將其傳入 merge 函式中作排序
    return merge(sortList(head), sortList(right))
};

function merge(l1,l2){
    let dummy = new ListNode(0)
    let curr = dummy
    
    // 兩兩比較，若 l1 比 l2 大，先將 l2 接到 cur 下，否則反之
    // 接上後，更新 cur 和 l1 or l2
    while(l1&&l2){
        if(l1.val>l2.val){
            curr.next = l2
            l2 = l2.next
        }else{
            curr.next = l1
            l1 = l1.next
        }
        curr = curr.next
    }
    
    // 如果其中 l1, 接完了，那就換 l2 
    // 最後回傳 dummy.next 以後的結果   
    curr.next = l1 ? l1 : l2
    return dummy.next
}

/**

* Definition for singly-linked list.

* function ListNode(val, next) {

* this.val = (val===undefined ? 0 : val)

* this.next = (next===undefined ? null : next)

* }

var sortList = function(head) {

if(!head || !head.next) return head

let slow = head

let fast = head.next

while(fast && fast.next){

slow = slow.next

fast = fast.next.next

}

const right = slow.next // 定義右半

slow.next = null // 將原始的 head 和右半切斷

// 反覆堆疊 sortList 的結果後，並將其傳入 merge 函式中作排序

return merge(sortList(head), sortList(right))

};

function merge(l1,l2){

let dummy = new ListNode(0)

let curr = dummy

// 兩兩比較，若 l1 比 l2 大，先將 l2 接到 cur 下，否則反之

// 接上後，更新 cur 和 l1 or l2

while(l1&&l2){

if(l1.val>l2.val){

curr.next = l2

l2 = l2.next

}else{

curr.next = l1

l1 = l1.next

}

curr = curr.next

}

// 如果其中 l1, 接完了，那就換 l2

// 最後回傳 dummy.next 以後的結果

curr.next = l1 ? l1 : l2

return dummy.next

}

206. Reverse Linked List

連結：https://leetcode.com/problems/reverse-linked-list/

var reverseList = function(head) {
    if(!head || !head.next) return head
    let temp = head
    head = reverseList(temp.next)
    temp.next.next = temp
    temp.next = null
    return head
};