iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 3
1
Software Development

LeetCode30系列 第 3

[LeetCode30] Day3 - 237. Delete Node in a Linked List

題目

題目給予了 singly-linked list中node的定義
每個node有一個key與指向下個node的指標。

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

請寫一個function,輸入參數為node的指標,不回傳,要做到把這個輸入的node刪除。

singly-linked list

將多個node串接起來,就成了linked list,因為node只有指向下個node的指標,被稱作singly-linked list。
如圖所示:
https://ithelp.ithome.com.tw/upload/images/20200918/20129147NXgVQvEYOP.png

特點

  • 不一定需要一個連續的空間
  • 相對於array,插入與刪除快速
    • array是一次分配一個連續的空間來儲存資料,刪除中間的值(這裡不是指刪掉值而已,而是把空間還給OS)需要重新分配空間,較為費時
  • 搜索較慢,須從頭循序查找
    • Time complexity O(n)

解法

因為規定function的輸入參數是要刪除的node,沒辦法直接改前一個node的next,。
但我們能換個方式,思路是把要刪除的node改成原本的下一個。
1. 把下個node的value覆寫到這個node。
2. 用一個tmp pointer儲存下個node(等下要釋放記憶體)
3. 調整pointer
如圖所示:
https://ithelp.ithome.com.tw/upload/images/20200918/20129147sWlgIx8NCN.jpg

class Solution {
public:
    void deleteNode(ListNode* node) {
        ListNode* tmp = node->next;
        node->val = node->next->val;
        node->next = node->next->next;
        delete tmp;
    }
};

https://ithelp.ithome.com.tw/upload/images/20200918/20129147oYIL1TK1qe.png


上一篇
[LeetCode30] Day2 - 461. Hamming Distance
下一篇
[LeetCode30] Day4 - 876. Middle of the Linked List
系列文
LeetCode3030
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言