700426. Delete in a Singly Linked List
Delete a Node in Single Linked List
Summary
This problem is about deleting a node from a singly linked list. Given a pointer to the node to be deleted, find and delete that node from the list. The main concept involved is understanding how linked lists work and how to traverse them.
Detailed Explanation
To solve this problem, we'll need to first understand how a singly linked list works. A singly linked list is a type of linked data structure where each element (or "node") points only to the next node in the sequence. This means that each node has a reference to the next node, but not the previous one.
The approach to solving this problem will be to traverse the linked list until we find the node to be deleted. Once found, we'll need to update the next pointer of the previous node to skip over the node to be deleted. If the node to be deleted is at the head of the list (i.e., it's the first node), then we'll simply update the head of the list to point to the node after the one to be deleted.
Here's a step-by-step breakdown of the solution:
- Start by initializing three pointers:
current,previous, andnodeToBeDeleted. Setcurrentto the head of the linked list, setprevioustonull, and setnodeToBeDeletedto the node we want to delete. - Traverse the linked list until we find the node to be deleted. We can do this by comparing each node's data to
nodeToBeDelete's data. When we find a match, updatepreviousto point to the current node and setcurrentto the next node in the list. - Once we've found the node to be deleted, check if it's at the head of the list (i.e.,
previousisnull). If it is, simply update the head of the list to point to the node after the one to be deleted. - If the node to be deleted is not at the head of the list, then update the next pointer of the previous node to skip over the node to be deleted.
Here's a diagram illustrating the process:
+----+ +----+
| A | --> | B |
+----+ +----+
(head of list)
+----+ +----+
| C | --> | node to be deleted | --> | D |
+----+ +----+
(traverse until we find the node to be deleted)
+----+ +----+
| E | --> | F |
+----+ +----+
(update previous and current pointers)
Time complexity: O(n), where n is the number of nodes in the linked list. Space complexity: O(1), as we only need a constant amount of space to store our pointers.
Optimized Solutions
Java
public class Solution {
public void deleteNode(SListNode node) {
if (node == null) return;
SListNode current = head;
while (current.next != node) current = current.next;
if (current.next == node) {
current.next = node.next;
} else {
head = node.next;
}
}
}