🔍 Problem Statement
Write a function to delete a node in a singly linked list, given only access to that node.
Note:
- The node to be deleted will not be the tail node.
- You have only access to the node to be deleted, and not the head of the linked list.
Example 1:
go
Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Example 2:
go
Input: head = [4,5,1,9], node = 1
Output: [4,5,9]
🧠 Approach
To solve this problem, we need to delete the node in the linked list. Since we are only given access to the node to be deleted and not the head, the approach is to copy the value of the next node into the current node, and then delete the next node.
Steps:
- Copy the value of the next node to the current node.
- Set the
next pointer of the current node to the node after the next one (i.e., skip the next node).
- This approach avoids the need to traverse the entire list or access the head.
Why this works:
By copying the value from the next node and then adjusting the pointers, the current node becomes effectively deleted, and the list is updated without having access to the head.
✅ Go Implementation
go
package main
import "fmt"
// Definition for singly-linked list.
type ListNode struct {
Val int
Next *ListNode
}
// Function to delete a node in a linked list
func deleteNode(node *ListNode) {
// Copy the value of the next node to the current node
node.Val = node.Next.Val
// Skip the next node by pointing to the node after the next one
node.Next = node.Next.Next
}
// Helper function to create a linked list from a slice of values
func createLinkedList(values []int) *ListNode {
if len(values) == 0 {
return nil
}
head := &ListNode{Val: values[0]}
current := head
for i := 1; i < len(values); i++ {
current.Next = &ListNode{Val: values[i]}
current = current.Next
}
return head
}
// Helper function to print the linked list
func printLinkedList(head *ListNode) {
current := head
for current != nil {
fmt.Print(current.Val)
if current.Next != nil {
fmt.Print(" -> ")
}
current = current.Next
}
fmt.Println()
}
// Test the deleteNode function
func main() {
// Example 1: Input linked list [4,5,1,9], node = 5
head := createLinkedList([]int{4, 5, 1, 9})
nodeToDelete := head.Next // Node with value 5
deleteNode(nodeToDelete)
printLinkedList(head) // Output: 4 -> 1 -> 9
// Example 2: Input linked list [4,5,1,9], node = 1
head2 := createLinkedList([]int{4, 5, 1, 9})
nodeToDelete2 := head2.Next.Next // Node with value 1
deleteNode(nodeToDelete2)
printLinkedList(head2) // Output: 4 -> 5 -> 9
}
🧑💻 Explanation of the Code
deleteNode function:
- The function takes a node to delete. The deletion is achieved by:
- Copying the value of the next node into the current node.
- Adjusting the current node's
next pointer to skip over the next node (i.e., point it to the node after the next one).
- Helper functions:
createLinkedList: Creates a linked list from a slice of integers.printLinkedList: Prints the linked list in a readable format.
main function:
- In the
main function, we test the deleteNode function by deleting nodes in two different linked lists and printing the results.
📦 Example Usage
go
func main() {
// Example 1: Input linked list [4,5,1,9], node = 5
head := createLinkedList([]int{4, 5, 1, 9})
nodeToDelete := head.Next // Node with value 5
deleteNode(nodeToDelete)
printLinkedList(head) // Output: 4 -> 1 -> 9
// Example 2: Input linked list [4,5,1,9], node = 1
head2 := createLinkedList([]int{4, 5, 1, 9})
nodeToDelete2 := head2.Next.Next // Node with value 1
deleteNode(nodeToDelete2)
printLinkedList(head2) // Output: 4 -> 5 -> 9
}
Example Output:
rust
4 -> 1 -> 9
4 -> 5 -> 9
⏱️ Time & Space Complexity
- Time Complexity: O(1)
- The time complexity is constant because we only perform a few pointer assignments, irrespective of the size of the linked list.
- Space Complexity: O(1)
- The space complexity is constant since we don't use any additional data structures and modify the list in-place.
This solution efficiently handles the deletion of a node in a linked list when only given access to that node, with both time and space complexity being optimal.