Coding

Delete Node in a Linked List O(1)

Asked at

Amazon

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Write a function to delete a node in a singly-linked list, given only access to that node.

You will not be given access to the head of the list, instead you will be given a reference to the node that needs to be deleted. It is guaranteed that the node to be deleted is not the tail of the list.

You must modify the linked list in-place without returning anything.

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.

**Input: **head = [1,2,3,4], node = 3 **Output: **[1,2,4] Explanation: You are given the third node with value 3, remove it in-place.

Input: head = [1,2], node = 1

The number of nodes in the list is in the range [2, 1000]
-1000 <= Node.val <= 1000
The given node is not the tail and is guaranteed to be in the list
The linked list will have at least two nodes

cpp

class Solution {
public:
    void deleteNode(ListNode* node) {
        // Your code goes here
    }
};

java

class Solution {
    public void deleteNode(ListNode node) {
        // Your code goes here
    }
}

python

class Solution:
    def deleteNode(self, node):
        # Your code goes here

javascript

class Solution {
    deleteNode(node) {
        // Your code goes here
    }
}

csharp

class Solution {
    public void DeleteNode(ListNode node) {
        // Your code goes here
    }
}

func deleteNode(node *ListNode) {
    // Your code goes here
}

Stuck? Show a way to structure it+

01Copy the next node's value into the given node.
02Redirect the given node's next pointer to skip its next node.
03Explain why this is logically deleting the given node.
04Rely on the guarantee that the node is not the tail.

Reference answer

Without a head or predecessor pointer, you cannot unlink the given node itself. Instead, copy node.next.val into node.val, then set node.next = node.next.next. The list now has the same observable values as if the original node were deleted; physically, its successor was removed. This is O(1) time and O(1) space. It cannot work for the tail because there is no successor to copy, which is why the problem explicitly rules that case out. In languages with manual memory management, release the bypassed node if ownership requires it.

Then expect these follow-ups

Why is true deletion impossible with only this node in a singly linked list?
Tests: data-structure reasoning
How does a doubly linked list change the answer?
Tests: pointer design

Hiring now

Software engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY

Or practice this question first

Next question