LeetCode-237. Delete Node in a Linked List

LeetCode-237. Delete Node in a Linked List

難度: medium

There is a singly-linked list head and we want to delete a node node in it.

You are given the node to be deleted node. You will not be given access to the first node of head.

All the values of the linked list are unique, and it is guaranteed that the given node node is not the last node in the linked list.

Delete the given node. Note that by deleting the node, we do not mean removing it from memory. We mean:

• The value of the given node should not exist in the linked list.
• The number of nodes in the linked list should decrease by one.
• All the values before node should be in the same order.
• All the values after node should be in the same order.

Custom testing:

• For the input, you should provide the entire linked list head and the node to be given node. node should not be the last node of the list and should be an actual node in the list.
• We will build the linked list and pass the node to your function.
• The output will be the entire list after calling your function.

 

Example 1:

Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.

Example 2:

Input: head = [4,5,1,9], node = 1
Output: [4,5,9]
Explanation: You are given the third node with value 1, the linked list should become 4 -> 5 -> 9 after calling your function.

Constraints:

• The number of the nodes in the given list is in the range [2, 1000].
• -1000 <= Node.val <= 1000
• The value of each node in the list is unique.
• The node to be deleted is in the list and is not a tail node.

解題流程

1. 先看懂題目想描述甚麼情境
2. 開始想像程式運作該經過哪些流程
3. 將經過的流程所需的判斷跟細節列出
4. 實作列出的流程

先看懂題目想描述甚麼情境

應該是要刪除鍊表的某一個node，但是它只提供你從要刪除的node開始的鍊表，但要想辦法將要刪除的node前一個node跟後一個node連結在一起，這樣就可以刪除要刪除的node(因為沒有其他node指向它了)。

但在沒有辦法取得刪除node的前一個node的狀況下，要如何將前一個node跟後一個連起來呢?
這裡就是題目困難的部分 (ps: 因為想破頭還沒想到所以後來參考其他人想法 XD

開始想像程式運作該經過哪些流程

首先要注意題目是要修改原本的鍊表而不是再創一個
要刪除的node不會是鍊表中的最後一個node
另外要注意題目沒有提到怎麼刪除，但只有說最後刪完後，鍊表的”值”會變成少了要刪掉的那一個
真心覺得如果題目有提出是刪掉某個值，而不是強調某個node，可能會比較好解，或許就是這題希望考生學會要變通思考吧?

其實可以把目前的node(要刪除的node)的值等於他的下一個node的值，然後把目前的node連到下下一個node，就可以達到不影響前一個node指向目前node，但鍊表看起來是少掉目標的node。

這邊可以不用設條件大膽的寫取得要刪除的node的下一個，因為條件有說明它不會是鍊表的最尾端，表示後面一定會有node，至於也不用特別針對目標的node的下下一個node設條件判斷是否有node，因為如果有下下一個node沒有，也就只是目標的node指向null，也算是斷掉跟原本node.next的連接。

將經過的流程所需的判斷跟細節列出

• 取得目前node的下一個node
• 取得node.next 的val
• 將目前node指向node.next 的下一個(node.next.next)
• 將目前node.val = node.next 的val

實作列出的流程

typescript

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

/**
 Do not return anything, modify it in-place instead.
 */
function deleteNode(node: ListNode | null): void {
    const nextNode = node.next;
    const nodeVal = nextNode.val;
    node.next = nextNode.next;
    node.val = nodeVal;
};

更好的方法

https://leetcode.com/problems/delete-node-in-a-linked-list/solutions/2697170/typescript-solution-super-duper-easy-o-1/?languageTags=typescript

其實不用寫變數暫存，直接改掉目標node的 val 為next.val 跟連接的next為下下一個就好。

function deleteNode(root: ListNode | null): void {
    root.val = root.next.val;
    root.next = root.next.next;
}

感謝閱讀，如果有錯誤或是講得不清楚的部分，再請留言指教