02.03. Delete Middle Node

Description

Implement an algorithm to delete a node in the middle (i.e., any node but the first and last node, not necessarily the exact middle) of a singly linked list, given only access to that node.

Example:

Input: the node c from the linked list a->b->c->d->e->f

Output: nothing is returned, but the new linked list looks like a->b->d->e->f

Solutions

Solution 1: Node Assignment

Thinking

Deletion usually needs the predecessor. Only the target node is given, and it is not the tail, so there is no way to walk backward.

The observable effect is that this position’s value and successor link vanish. Copying the next value into the current node and skipping the next node looks like a deletion to the caller.

The two assignments node.val = node.next.val and node.next = node.next.next suffice in constant time and space.

We can replace the value of the current node with the value of the next node, and then delete the next node. This way, we can achieve the purpose of deleting the current node.

The time complexity is \(O(1)\), and the space complexity is \(O(1)\).

Python3JavaC++GoJavaScriptSwift

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None


class Solution:
    def deleteNode(self, node):
        node.val = node.next.val
        node.next = node.next.next

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        node->val = node->next->val;
        node->next = node->next->next;
    }
};

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteNode(node *ListNode) {
    node.Val = node.Next.Val
    node.Next = node.Next.Next
}

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} node
 * @return {void} Do not return anything, modify node in-place instead.
 */
var deleteNode = function (node) {
    node.val = node.next.val;
    node.next = node.next.next;
};

/**
*    public class ListNode {
*        var val: Int
*        var next: ListNode?
*        init(_ x: Int) {
*            self.val = x
*            self.next = nil
*        }
*    }
*/
class Solution {
    func deleteNode(_ node: ListNode?) {
        guard let node = node, let next = node.next else { return }
        node.val = next.val
        node.next = next.next
    }
}

02.03. Delete Middle Node

Description

Solutions

Solution 1: Node Assignment

Comments