LeetCode Delete Node in a Linked List: O(1) Time and Space

Overview

LeetCode Delete Node in a Linked List: We can solve it by swapping the current node and the next node in O(1) Time and Space.

LeetCode Delete Node in a Linked List

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.

LeetCode Delete Node in a Linked List: O(1) Time and Space Solution

A lot of people might just come up with the following O(N) time solution by shifting the remaining portion of the giving linked list to left by one node as the following code shows, it could be accepted by LeetCode OJ to pass this delete node in a linked list problem though:

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

	public void deleteNode(ListNode node) {

		ListNode p1 = node;
		ListNode p2 = node.next;

		while (p2.next != null) {
			p1.val = p2.val;
			p1 = p2;
			p2 = p2.next;
		}

		p1.val = p2.val;
		p1.next = null;
	}
}

However, there could be a much more elegant and simple solution with O(1) time and space cost in two lines of Java code. Think about the delete node in a linked list problem description again: “delete a node (except the tail)”, and do we really care about the remaining nodes except the given node to delete and its next node? So here we are, the following 2 lines code could be accepted by LeetCode OJ too to pass this delete node in a linked list problem:

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

	public void deleteNode(ListNode node) {

		node.val = node.next.val;
		node.next = node.next.next;

	}
}

You might want to check out this similar problem as well for further references: LeetCode Remove Linked List Elements: Iterative vs Recursive

Summary

LeetCode Delete Node in a Linked List: We can solve it by swapping the current node and the next node in O(1) Time and Space.

Written on July 26, 2015