LeetCode-Linked List 鏈結串列

相關題目彙整筆記

🚪 前往筆記：資料結構-Linked List 鏈結串列

📔 共整理 6 題相關的題目：

237. Delete Node in a Linked List

203. Remove Linked List Elements

83. Remove Duplicates from Sorted List

876. Middle of the Linked List

21. Merge Two Sorted Lists

206. Reverse Linked List

237. Delete Node in a Linked List

查看題目，請點這裡 🔗

var deleteNode = function(node) {
    node.val = node.next.val
    node.next = node.next.next;
};

把下一個 node 的值複製過來，再把 next 指向next, next (移除掉該 node)。

203. Remove Linked List Elements

查看題目，請點這裡 🔗

var removeElements = function(head, val) {
    let dummy = new ListNode(-1);
    dummy.next = head;
    let curr = dummy;
    
    while(curr.next) {
        if(curr.next.val == val) {
            curr.next = curr.next.next;
        }else {
            curr = curr.next;
        }
    }
    return dummy.next
};

首先，製造一個 dummy 節點，指向 head。 curr 在 dummy 上面移動，如果值跟指定的 val 相等則指向下一個，其他情況則直接移動 curr。最後 return dmmy.next。

83. Remove Duplicates from Sorted List

查看題目，請點這裡 🔗

var deleteDuplicates = function(head) {
    let dummy = new ListNode(-101);
    dummy.next = head;
    let curr = dummy;
    while(curr.next) {
        if(curr.val == curr.next.val) {
            curr.next = curr.next.next
        } else {
            curr = curr.next
        }
    }
    return dummy.next
    
};

這題跟上方題目非常相似，特別要注意的是 new ListNode 放 -101，因為題目給定-100 <= Node.val <= 100 。

876. Middle of the Linked List

查看題目，請點這裡 🔗

var middleNode = function(head) {
    let curr = head;
    let count = 0;
    while(curr) {
        count++;
        curr = curr.next
    }
    let num = Math.floor(count/2) //計算要拿掉幾個
    curr = head;
    while(num > 0) {
        curr = curr.next;
        num--;
    }
    return curr;
};

首先讓 curr 指向 head，接著用 while 迴圈去計算整個 list 的長度。num 計算要拿去幾個節點。curr 不斷往下一個指，直到指到要的節點即 return。

21. Merge Two Sorted Lists

查看題目，請點這裡 🔗

var mergeTwoLists = function(l1, l2) {
    let dummy = new ListNode(-1);
    let curr = dummy;
    
    if(l1 == null) {return l2};
    if(l2 == null) {return l1};
    
    while(l1 != null || l2 != null) {
        if(l1 == null) {
            curr.next = l2;
            break;
        }
        if(l2 == null) {
            curr.next = l1;
            break;
        }
        if(l1.val <= l2.val) {
            curr.next = l1;
            l1 = l1.next;
            curr = curr.next;
        } else {
            curr.next = l2;
            l2 = l2.next;
            curr = curr.next;
        }
    }
    
    return dummy.next;
    
};

設定 dummy 來記節點。先判斷 l1 , l2 若為空的 linked list，直接回傳另一個linked list 即結束。進到 while 迴圈，若有其一的節點指向 null，後續銜接另一個 list 所有剩下的節點。若都還有值的情況去做比較，比較小的會被 curr 串上 dummy list，最後回傳 dummy.next。

206. Reverse Linked List

查看題目，請點這裡 🔗

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

解法：迭代作法 Iteratively
先將 curr 設定為 head，pre 設定成 null。curr 不是 null 的情況下，指定好 next 給 curr 下一個值(因為會調整到 curr，所以先記起來)，curr. next 反向指向 pre，指完後 pre 更新到 curr 的位置， curr 往前挪動到剛剛預先記好的 next 位置。最後 return pre。

若後續有寫到相關不錯的題目，會持續更新此筆記。

📐✏️ 📏

若有任何錯誤請在下方留言～🙏 Thanks!