LeetCode《初級演算法》連結串列之刪除連結串列的倒數第N個節點 -- JavaScript

語言: CN / TW / HK

題目

題目連結:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn2925/

image.png


題解

1、兩次遍歷刪除給定節點

連結串列節點的刪除,一般思路都是先找到要刪除節點的前一個節點,然後再刪除需要刪除的節點;這裡先遍歷連結串列得到連結串列的長度,再遍歷到自定節點的前一個節點來對給定節點進行刪除; ```js / * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ / * @param {ListNode} head * @param {number} n * @return {ListNode} */ var removeNthFromEnd = function(head, n) {

let len = 0;
let temp = head;

// 獲取連結串列長度
while(temp !== null) {
    len++;
    temp = temp.next;
}

// 處理刪除第一個節點的情況
if(n === len) {
    return head.next;
}

// 找到指定位置節點的前一個節點,並將指定節點刪除
len = len - n;
temp = head;
for(let i = 2;i <= len;i++) {

    temp = temp.next;
}

temp.next = temp.next.next; // js 中自動回收記憶體,只要將指向物件的引用去掉就行;

return head;

}; ``` 注意邊界條件,當要刪除第一個節點時因為連結串列沒有頭節點,使得和刪除其它節點的操作並不一致,因此要對刪除第一個節點做額外操作;

2、使用一次遍歷刪除指定節點

空間換時間是普遍規律;

如果想要一次遍歷就將指定節點給刪除,我們可以通過先使用陣列將所有節點的地址存下來;

然後利用順序儲存的陣列的隨機訪問直接獲得指定節點的前一個節點;

最後對指定節點進行刪除;

```js

/ * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ / * @param {ListNode} head * @param {number} n * @return {ListNode} */ var removeNthFromEnd = function(head, n) {

let len = 0;
let temp = head;

let addressArr = [];

while(temp !== null) {

    len++;
    addressArr.push(temp);
    temp = temp.next;
}

// 處理刪除第一個節點的情況
if(n === len) {
    return head.next;
}

addressArr[len - n - 1].next = addressArr[len - n].next;
addressArr = null;

return head;

}; ```

3、使用遞迴實現

也可以使用遞迴實現,退出遞迴棧的過程計數,這樣就可以實現倒數計數對指定節點進行刪除; 要注意對當需要刪除的節點是第一個節點時的處理;

```js / * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ / * @param {ListNode} head * @param {number} n * @return {ListNode} */ var removeNthFromEnd = function(head, n) { // 這個標誌用來處理當刪除的節點是第一個節點時,便於後面對其進行處理 let flag = false;

function deleteNode(initialHead,head,n) {

    if(head === null){
        return n;
    }

    m = deleteNode(initialHead,head.next,n);

    if(m === 0) {
        head.next = head.next.next;
    }else if(m === 1 && head === initialHead) {  // 當要刪除的節點是最後一個節點

        flag = true; 
        return ;
    }


    return m -1;
}

deleteNode(head,head,n); // 在寫js的時候經常會這樣,定義了函式忘了執行...

if(flag) {
    head = head.next;
}

return head;

}; ```

4、給連結串列新增上頭節點以統一操作

連結串列沒有頭節點帶來刪除操作的不一致,因此先給連結串列節點加上一個頭節點,然後再使用上面的方法處理連結串列;

以下是先給連結串列加上頭節點,然後再兩次遍歷刪除節點的程式碼:

```js / * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ / * @param {ListNode} head * @param {number} n * @return {ListNode} */ var removeNthFromEnd = function(head, n) {

const vhead = new ListNode(null,head);

let len = 0;
let temp = head;

// 獲取連結串列長度
while(temp !== null) {
    len++;
    temp = temp.next;
}


// 找到指定位置節點的前一個節點,並將指定節點刪除
len = len - n;
temp = vhead;
for(let i = 1;i <= len;i++) {

    temp = temp.next;
}

temp.next = temp.next.next; // js 中自動回收記憶體,只要將指向物件的引用去掉就行;


return vhead.next;

};

```



大家如果有更好的思路和解法,歡迎大家一起來討論啊~

這是使用 JavaScript 對 LeetCode《初級演算法》的每道題的總結和實現的其中一篇,彙總篇在這裡:

https://juejin.cn/post/7006692002125316103