grid47 Exploring patterns and algorithms
Aug 28, 2024
9 min read
Solution to LeetCode 707: Design Linked List Problem
Design a custom linked list that supports multiple operations. You can choose to implement it using a singly or doubly linked list. Implement the following methods in the MyLinkedList class:
Problem
Approach
Steps
Complexity
Input: The input consists of the following method calls: 'MyLinkedList', 'addAtHead', 'addAtTail', 'addAtIndex', 'get', 'deleteAtIndex'. Each of these methods will take the necessary arguments as specified.
Example:
Constraints:
Output: The output consists of a series of responses to the methods called. For each 'get' operation, the value of the node at the specified index is returned, or -1 if the index is invalid. For other operations, the response is 'null'.
Example:
Constraints:
Goal: Implement a linked list with operations to retrieve, add, and delete nodes at specified indices.
Steps:
• Initialize a linked list with a head pointer to track the first node.
• Implement methods to add nodes at the head, tail, or a specific index.
• Implement a method to retrieve the value of a node at a specific index.
• Implement a method to delete a node at a specific index.
Goal: You are not allowed to use any built-in linked list libraries.
Steps:
• 0 <= index, val <= 1000
• At most 2000 calls will be made to the methods 'get', 'addAtHead', 'addAtTail', 'addAtIndex', and 'deleteAtIndex'.
Assumptions:
• All operations are performed in constant time where possible.
• Explanation: In this example, the linked list is initialized as an empty list. The sequence of operations adds elements at the head and tail, inserts an element at a specific index, retrieves an element at an index, deletes an element, and retrieves the element at that index again after deletion.
Approach: The approach involves maintaining a linked list with nodes containing a value and a reference to the next node. The operations modify or access nodes based on the index provided.
Observations:
• A singly linked list can efficiently handle these operations with proper indexing.
• Node insertion and deletion at specific indices require traversing the list, which is key to handling this problem.
• We will maintain a reference to the head of the linked list and adjust the pointers when adding or removing nodes.
Steps:
• Define a Node class with value and next attributes.
• Create methods to handle the four operations: get, addAtHead, addAtTail, addAtIndex, and deleteAtIndex.
• Use a simple for loop to iterate through the list when performing insertion and deletion at specific indices.
Empty Inputs:
• Operations on an empty list (e.g., get, deleteAtIndex).
Large Inputs:
• Handling up to 2000 operations efficiently.
Special Values:
• When index equals 0 or the end of the list.
Constraints:
• Ensure that invalid indices are handled gracefully by returning -1 or skipping invalid operations.
int val;
Node* next;
Node(int x): val(x), next(nullptr) {}
};
classMyLinkedList {
int sz;
Node* head;
public:MyLinkedList(): sz(0), head(nullptr) { }
intget(int index) {
if(index <0|| index >= sz)
return-1;
else {
Node* curr = head;
for(int i =0; i < index;i++)
curr = curr->next;
return curr->val;
}
}
voidaddAtHead(int val) {
addAtIndex(0, val);
}
voidaddAtTail(int val) {
addAtIndex(sz, val);
}
voidaddAtIndex(int index, int val) {
if(index > sz || index <0) return;
Node* cur = head;
Node* new_node =new Node(val);
if(index ==0) {
new_node->next = head;
head = new_node;
} else {
for(int i =0; i < index -1; i++)
cur = cur->next;
new_node->next = cur->next;
cur->next = new_node;
}
sz++;
}
voiddeleteAtIndex(int index) {
if(index >= sz || index <0) return;
if(index ==0) {
Node* nxt = head->next;
delete head;
head = nxt;
} else {
Node* cur = head;
for(int i =0; i < index -1; i++)
cur = cur->next;
Node* nxt = cur->next->next;
delete cur->next;
cur->next = nxt;
}
sz--;
}
};
/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList* obj = new MyLinkedList();
* int param_1 = obj->get(index);
* obj->addAtHead(val);
* obj->addAtTail(val);
* obj->addAtIndex(index,val);
* obj->deleteAtIndex(index);
1 : Variable Initialization
int val;
Declare a variable 'val' to store the value of the node.
2 : Node Declaration
Node* next;
Declare a pointer 'next' to the next node in the list.
3 : Constructor
Node(int x): val(x), next(nullptr) {}
Constructor to initialize a node with a given value 'x' and set 'next' to nullptr.
4 : Class Declaration
classMyLinkedList {
Define the MyLinkedList class which holds the methods and variables related to the linked list.
5 : Variable Declaration
int sz;
Declare an integer variable 'sz' to store the size of the linked list.
6 : Node Declaration
Node* head;
Declare a pointer 'head' to point to the first node in the linked list.
7 : Public Access Modifier
public:
Indicates that the following methods and variables are accessible outside the class.
8 : Constructor
MyLinkedList(): sz(0), head(nullptr) { }
Constructor to initialize the linked list with size 0 and head as nullptr.
9 : Method Declaration
intget(int index) {
Define the 'get' method to retrieve the value of the node at the specified index.
10 : Edge Case Handling
if(index <0|| index >= sz)
Check if the index is valid. If not, return -1.
11 : Return Statement
return-1;
Return -1 when the index is out of bounds.
12 : Conditional Branch
else {
Start the else block to handle valid index.
13 : Node Traversal
Node* curr = head;
Create a pointer 'curr' to traverse the linked list starting from the head.
14 : Loop
for(int i =0; i < index;i++)
Use a loop to traverse the list until the specified index.
15 : Pointer Update
curr = curr->next;
Move the 'curr' pointer to the next node.
16 : Return Statement
return curr->val;
Return the value of the node at the specified index.
17 : Method Declaration
voidaddAtHead(int val) {
Define the 'addAtHead' method to add a new node at the head of the list.
18 : Method Call
addAtIndex(0, val);
Call 'addAtIndex' method to add the new node at index 0.
19 : Method Declaration
voidaddAtTail(int val) {
Define the 'addAtTail' method to add a new node at the end of the list.
20 : Method Call
addAtIndex(sz, val);
Call 'addAtIndex' method to add the new node at the tail (end of the list).
21 : Method Declaration
voidaddAtIndex(int index, int val) {
Define the 'addAtIndex' method to insert a node at a specific index.
22 : Edge Case Handling
if(index > sz || index <0) return;
Check if the index is valid. If not, do nothing.
23 : Node Creation
Node* new_node =new Node(val);
Create a new node with the given value 'val'.
24 : Conditional Branch
if(index ==0) {
Start the block to handle insertion at index 0.
25 : Node Update
new_node->next = head;
Set the 'next' pointer of the new node to point to the current head.
26 : Pointer Update
head = new_node;
Update the head pointer to point to the new node.
27 : End of Conditional Block
} else {
Handle the insertion at other indices.
28 : Node Traversal
for(int i =0; i < index -1; i++)
Traverse the list to find the node just before the insertion point.
29 : Pointer Update
cur = cur->next;
Move the 'cur' pointer to the next node.
30 : Linking Nodes
new_node->next = cur->next;
Set the 'next' pointer of the new node to point to the next node after 'cur'.
31 : Pointer Update
cur->next = new_node;
Set the 'next' pointer of 'cur' to point to the new node.
32 : Size Update
sz++;
Increment the size of the linked list after adding the new node.
33 : Method Declaration
voiddeleteAtIndex(int index) {
Define the 'deleteAtIndex' method to delete a node at a specified index.
34 : Edge Case Handling
if(index >= sz || index <0) return;
Check if the index is valid. If not, do nothing.
35 : Conditional Branch
if(index ==0) {
Start block to delete the node at index 0.
36 : Pointer Update
Node* nxt = head->next;
Store the pointer to the next node in 'nxt'.
37 : Node Deletion
delete head;
Delete the current head node.
38 : Pointer Update
head = nxt;
Update the head pointer to point to the next node.
39 : End of Conditional Block
} else {
Handle the deletion for other indices.
40 : Node Traversal
Node* cur = head;
Traverse the list to find the node just before the one to delete.
41 : Loop
for(int i =0; i < index -1; i++)
Traverse through the nodes until reaching the desired index.
42 : Pointer Update
cur = cur->next;
Move the 'cur' pointer to the next node.
43 : Link Update
Node* nxt = cur->next->next;
Save the pointer to the next node after the one to delete.
44 : Node Deletion
delete cur->next;
Delete the node at the specified index.
45 : Pointer Update
cur->next = nxt;
Update the 'next' pointer of 'cur' to skip the deleted node.
46 : Size Update
sz--;
Decrement the size of the linked list after deleting a node.
Best Case: O(1) for get, addAtHead, and addAtTail.
Average Case: O(n) for addAtIndex and deleteAtIndex where n is the size of the list.
Worst Case: O(n) for all operations where n is the size of the list.
Description: The time complexity for operations like 'get', 'addAtHead', and 'addAtTail' is O(1), but for operations that require traversing the list (e.g., addAtIndex and deleteAtIndex), it is O(n).
Best Case: O(1), for an empty list or when minimal memory is used.
Worst Case: O(n), where n is the number of nodes in the list.
Description: Space complexity is proportional to the number of nodes in the list, as each node occupies space.
