Linked List¶
Single Linked List¶
Basic Operations¶
/*
QUESTION:-
Construct the linked list from arr and return the head of the linked list.
Example 1:
Input:
n = 5
arr = [1,2,3,4,5]
Output:
1 2 3 4 5
Explanation: Linked list for the given array will be 1->2->3->4->5.
Example 2:
Input:
n = 2
arr = [2,4]
Output:
2 4
Explanation: Linked list for the given array will be 2->4.
APPROACH:-
The approach to construct a linked list from an array is as follows:
1. Create the head node of the linked list using the first element of the array.
2. Initialize a current pointer to the head node.
3. Traverse the array starting from the second element.
4. For each element in the array, create a new node and assign the element as its data.
5. Set the `next` pointer of the current node to the newly created node.
6. Update the current pointer to the newly created node.
7. Repeat steps 4-6 until all elements in the array are processed.
8. Return the head node of the constructed linked list.
CODE:-
*/
Node* constructLL(vector<int>& arr) {
Node* head = new Node(arr[0]);
Node* curr = head;
for(int i=1; i<arr.size(); i++){
curr->next = new Node(arr[i]);
curr = curr->next;
}
return head;
}
/*
TIME COMPLEXITY:- O(n)
SPACE COMPLEXITY:- O(n)
*/
/*
QUESTION:-
Create a link list of size N according to the given input literals. Each integer input is accompanied by an indicator which can either be 0 or 1. If it is 0, insert the integer in the beginning of the link list. If it is 1, insert the integer at the end of the link list.
Hint: When inserting at the end, make sure that you handle NULL explicitly.
Example 1:
Input:
LinkedList: 9->0->5->1->6->1->2->0->5->0
Output: 5 2 9 5 6
Explanation:
Length of Link List = N = 5
9 0 indicated that 9 should be
inserted in the beginning. Modified
Link List = 9.
5 1 indicated that 5 should be
inserted in the end. Modified Link
List = 9,5.
6 1 indicated that 6 should be
inserted in the end. Modified Link
List = 9,5,6.
2 0 indicated that 2 should be
inserted in the beginning. Modified
Link List = 2,9,5,6.
5 0 indicated that 5 should be
inserted in the beginning. Modified
Link List = 5,2,9,5,6.
Final linked list = 5, 2, 9, 5, 6.
Example 2:
Input:
LinkedList: 5->1->6->1->9->1
Output: 5 6 9
The approach to solving this problem is as follows:
1. Initialize an empty linked list by setting the `head` pointer to `NULL`.
2. Iterate through the given input literals.
3. If the indicator is 0, insert the integer at the beginning of the linked list by calling the `insertAtBeginning` function. This function creates a new node with the given integer value and inserts it at the beginning of the linked list.
4. If the indicator is 1, insert the integer at the end of the linked list by calling the `insertAtEnd` function. This function creates a new node with the given integer value and inserts it at the end of the linked list.
5. After iterating through all the input literals, the resulting linked list will be the desired output.
Time complexity of this approach is O(N), where N is the number of input literals, as we need to iterate through all the literals to construct the linked list.
Space complexity is O(1) as we are not using any extra space that grows with the input size. We only need a constant amount of space to store the pointers and temporary variables.
CODE:-
*/
Node *insertAtBegining(Node *head, int x) {
if(head==NULL)
return new Node(x);
Node* temp = new Node(x);
temp->next = head;
return temp;
}
//Function to insert a node at the end of the linked list.
Node *insertAtEnd(Node *head, int x) {
if(head==NULL)
return new Node(x);
Node* curr = head;
while(curr->next){
curr = curr->next;
}
curr->next = new Node(x);
return head;
}
/*
QUESTION:-
Given a singly linked list and an integer x.Delete xth node from the singly linked list.
Example 1:
Input: 1 -> 3 -> 4
x = 3
Output: 1 -> 3
Explanation:
After deleting the node at 3rd
position (1-base indexing), the
linked list is as 1 -> 3.
Example 2:
Input: 1 -> 5 -> 2 -> 9
x = 2
Output: 1 -> 2 -> 9
Explanation:
After deleting the node at 2nd
position (1-based indexing), the
linked list is as 1 -> 2 -> 9.
APPROACH:-
1. If the given position is 1, it means the node to be deleted is the first node. In this case, we simply update the head pointer to the next node and return the new head.
2. Initialize a counter `cnt` to 1 and a pointer `curr` to the head of the linked list.
3. Traverse the linked list by moving the `curr` pointer to the next node until the counter `cnt` reaches the position just before the node to be deleted.
4. Once we reach the position just before the node to be deleted, we update the `next` pointer of the current node to skip the next node and point to the node after it.
5. Return the head pointer of the modified linked list.
Time complexity of this approach is O(N), where N is the number of nodes in the linked list. We may need to traverse the linked list until we reach the desired position.
Space complexity is O(1) as we are not using any extra space that grows with the input size. We only need a constant amount of space to store the counter variable and the temporary pointer.
CODE:-
*/
Node* deleteNode(Node *head,int x)
{
if(x==1)
return head->next;
int cnt = 1;
Node* curr = head;
while(cnt<x-1){
cnt++;
curr = curr->next;
}
curr->next = curr->next->next;
return head;
}
/*
QUESTION:-
Given a singly linked list. The task is to find the length of the linked list, where length is defined as the number of nodes in the linked list.
Example 1:
Input:
LinkedList: 1->2->3->4->5
Output: 5
Explanation: Count of nodes in the
linked list is 5, which is its length.
Example 2:
Input:
LinkedList: 2->4->6->7->5->1->0
Output: 7
Explanation: Count of nodes in the
linked list is 7. Hence, the output
is 7.
APPROACH:-
1. Initialize a variable `cnt` to 0 to keep track of the count.
2. Start with the `curr` pointer pointing to the head of the linked list.
3. Iterate through the linked list by moving the `curr` pointer to the next node in each iteration.
4. Increment the count `cnt` by 1 for each node encountered.
5. Continue the iteration until the `curr` pointer becomes NULL, indicating the end of the linked list.
6. Return the final count `cnt` as the result.
Time complexity of this approach is O(N), where N is the number of nodes in the linked list. We need to visit each node once to count them.
Space complexity is O(1) as we are not using any extra space that grows with the input size. We only need a constant amount of space to store the count variable and the temporary pointer.
CODE:-
*/
int getCount(struct Node* head){
int cnt = 0;
Node* curr = head;
while(curr){
cnt++;
curr = curr->next;
}
return cnt;
}
/*
QUESTION:-
Given a linked list of n nodes and a key , the task is to check if the key is present in the linked list or not.
Example:
Input:
n = 4
1->2->3->4
Key = 3
Output:
True
Explanation:
3 is present in Linked List, so the function returns true.
APPROCACH:-
Just traverse the entire Linked List and if node's data matches with the target return true else return false.
TIME COMPLEXITY:- O(N)
SPACE COMPLEXITY:- O(1)
CODE:-
*/
bool searchKey(int n, struct Node* head, int key) {
struct Node* curr = head;
while(curr){
if(curr->data == key)
return true;
curr = curr->next;
}
return false;
}
Doubly Linked List¶
Basic Operations¶
/*
QUESTION:-
Given a doubly linked list of n elements. The task is to reverse the doubly linked list.
Example 1:
Input:
LinkedList: 3 <--> 4 <--> 5
Output: 5 4 3
Example 2:
Input:
LinkedList: 75 <--> 122 <--> 59 <--> 196
Output: 196 59 122 75
APPROACH:-
1. Initialize two pointers `curr` and `nxt` to traverse the linked list. Set `curr` to the head of the linked list.
2. In each iteration, store the next node in the `nxt` pointer to avoid losing the reference to the next node.
3. Swap the `next` and `prev` pointers of the current node (`curr`).
4. Check if the `prev` pointer of the current node (`curr->prev`) is `NULL`, which indicates that `curr` is the last node of the original linked list. If so, update the `ans` pointer to point to `curr` (the new head of the reversed linked list).
5. Move the `curr` pointer to the previous node (`curr = curr->prev`) using the stored `nxt` pointer.
6. Repeat steps 2-5 until `curr` becomes `NULL`, indicating that we have reached the end of the original linked list.
7. Return the `ans` pointer, which now points to the head of the reversed linked list.
Time complexity of this approach is O(N), where N is the number of nodes in the doubly linked list. We need to traverse the entire list once to reverse the links.
Space complexity is O(1) as we are using a constant amount of extra space to store temporary pointers during the reversal process.
*/
Node* reverseDLL(Node * head)
{
Node* curr = head;
Node* ans = NULL;
while(curr){
Node* nxt = curr->next;
curr->next = curr->prev;
curr->prev = nxt;
// this is to get the last node
if(curr->prev==NULL)
ans = curr;
curr = curr->prev;
}
return ans;
}
/*
QUESTION:-
Given a doubly-linked list, a position p, and an integer x. The task is to add a new node with value x at the position just after pth node in the doubly linked list.
Example 1:
Input:
LinkedList: 2<->4<->5
p = 2, x = 6
Output: 2 4 5 6
Explanation: p = 2, and x = 6. So, 6 is
inserted after p, i.e, at position 3
(0-based indexing).
Example 2:
Input:
LinkedList: 1<->2<->3<->4
p = 0, x = 44
Output: 1 44 2 3 4
Explanation: p = 0, and x = 44 . So, 44
is inserted after p, i.e, at position 1
(0-based indexing).
APPROACH:-
The approach to adding a node at a specific position in a doubly linked list is as follows:
1. Initialize a counter `cnt` to 0 and a pointer `curr` to the head of the linked list.
2. Traverse the linked list using the `curr` pointer until the `cnt` is less than the specified position.
3. Increment the `cnt` by 1 and move the `curr` pointer to the next node in each iteration.
4. Once the `cnt` reaches the desired position, create a new node with the given data.
5. Set the `next` pointer of the new node to the next node of the current node (`curr->next`) and the `prev` pointer of the new node to the current node (`curr`).
6. Update the `next` pointer of the current node (`curr->next`) to point to the new node.
7. If the new node is inserted in the middle of the list, update the `prev` pointer of the next node (`nxt`) to point to the new node.
8. The new node is successfully inserted into the linked list.
Time complexity of this approach is O(N), where N is the number of nodes in the doubly linked list. In the worst case, we may need to traverse the entire list to reach the desired position.
Space complexity is O(1) as we are using a constant amount of extra space to store temporary pointers during the insertion process.
CODE:-
*/
void addNode(Node *head, int pos, int data)
{
int cnt = 0;
Node* curr = head;
while(cnt<pos){
curr = curr->next;
cnt++;
}
Node* nxt = curr->next;
curr->next = new Node(data);
curr->next->prev = curr;
curr->next->next = nxt;
}
/*Given a doubly linked list and a position. The task is to delete a node from given position in a doubly linked list.
Example 1:
Input:
LinkedList = 1 <--> 3 <--> 4
x = 3
Output: 1 3
Explanation: After deleting the node at
position 3 (position starts from 1),
the linked list will be now as 1->3.
Example 2:
Input:
LinkedList = 1 <--> 5 <--> 2 <--> 9
x = 1
Output: 5 2 9
APPROACH:-
1. The function `deleteNode` takes in two parameters: `head_ref`, which is a pointer to the head of the doubly linked list, and `x`, which represents the position of the node to be deleted.
2. The variable `temp` is initialized as the `head_ref`, which is a pointer to the head node of the linked list.
3. If `x` is equal to 1, it means the node to be deleted is the head node. In this case, the `temp` pointer is moved to the next node, and the new `temp` pointer is returned as the new head of the linked list. This effectively deletes the original head node.
4. If `x` is greater than 1, the code enters a loop that iterates `x-1` times. This loop moves the `temp` pointer to the node just before the position to be deleted.
5. After the loop, the variable `previous` is assigned the value of `temp`, which represents the node just before the position to be deleted.
6. The `previous->next` pointer is adjusted to skip over the node to be deleted by assigning it the value of `temp->next->next`.
7. The `temp->prev` pointer is adjusted to point to the `previous` node, updating the backward link.
8. Finally, the updated `head_ref` is returned.
CODE:-
*/
Node* deleteNode(Node *head_ref, int x) {
Node* temp = head_ref;
// If the node to be deleted is the head node
if (x == 1) {
temp = temp->next;
return temp;
}
// Traverse to the node just before the position to be deleted
for (int i = 1; i < (x - 1); i++) {
temp = temp->next;
}
// Store the previous and next nodes of the node to be deleted
Node* previous = temp;
previous->next = temp->next->next;
temp->prev = previous;
return head_ref;
}
/*
Time Complexity:
- If the node to be deleted is the head node (position 1), the code performs a constant number of operations, resulting in a time complexity of O(1).
- If the node to be deleted is at any other position, the code traverses the linked list until it reaches the node just before the position to be deleted. This traversal requires visiting at most (x-1) nodes, where x is the position of the node to be deleted. Therefore, the time complexity in this case is O(x).
Space Complexity:
- The code uses a constant amount of extra space for variables (`temp`, `previous`). Hence, the space complexity is O(1).
In summary, the time complexity of the provided code is O(1) when deleting the head node and O(x) when deleting any other node, where x is the position of the node to be deleted. The space complexity is O(1).
*/
/*
Given a doubly linked list of n elements. The task is to reverse the doubly linked list.
Example 1:
Input:
LinkedList: 3 <--> 4 <--> 5
Output: 5 4 3
Example 2:
Input:
LinkedList: 75 <--> 122 <--> 59 <--> 196
Output: 196 59 122 75
APPROACH:-
1. The function `reverseDLL` takes in one parameter: `head`, which is a pointer to the head of the doubly linked list.
2. The variable `curr` is initialized with the `head` pointer, which represents the current node being processed.
3. The variable `ans` is initialized as `NULL`. It will store the new head of the reversed linked list.
4. The code enters a `while` loop, which continues until `curr` becomes `NULL`, indicating that all nodes have been processed.
5. Inside the loop, the variable `nxt` is assigned the value of `curr->next`, which represents the next node in the original list.
6. The next and previous pointers of the current node (`curr->next` and `curr->prev`) are swapped to reverse the links.
7. The `if` condition checks if `curr->prev` is `NULL`, indicating that `curr` is the last node in the original list (now the first node in the reversed list). In this case, the `ans` pointer is updated to store the new head of the reversed list.
8. The `curr` pointer is updated to `curr->prev`, which moves it to the previous node in the original list.
9. After the loop, the `ans` pointer now holds the new head of the reversed list. It is returned as the result.
CODE:-
*/
Node* reverseDLL(Node *head) {
Node* curr = head;
Node* ans = NULL;
while(curr) {
Node* nxt = curr->next;
curr->next = curr->prev;
curr->prev = nxt;
if(curr->prev == NULL)
ans = curr;
curr = curr->prev;
}
return ans;
}
/*
Time Complexity:
- The code iterates over each node of the doubly linked list exactly once, performing a constant number of operations for each node. Therefore, the time complexity is O(n), where n is the number of nodes in the linked list.
Space Complexity:
- The code uses a constant amount of extra space for variables (`curr`, `nxt`, `ans`). Hence, the space complexity is O(1).
*/
Medium Problems (Singly Linked List)¶
/*
QUESTION:-
Given the head of a singly linked list, return the middle node of the linked list.
If there are two middle nodes, return the second middle node.
Example 1:
Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3.
Example 2:
Input: head = [1,2,3,4,5,6]
Output: [4,5,6]
Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.
*/
/*
APPROACH:
-> To find the middle node of a linked list, we can use the two-pointer technique.
-> Initialize two pointers, slow and fast, to the head of the linked list.
-> Move the slow pointer one step at a time and the fast pointer two steps at a time.
-> When the fast pointer reaches the end of the list, the slow pointer will be at the middle node.
-> If the total number of nodes in the list is even, there will be two middle nodes, and the slow pointer will be at the first middle node.
-> To return the second middle node, we need to move the slow pointer one more step.
-> Finally, return the node pointed to by the slow pointer.
*/
// CODE:-
ListNode* middleNode(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
// TIME COMPLEXITY: O(N)
// SPACE COMPLEXITY: O(1)
/*
QUESTION:-
Given the head of a singly linked list, reverse the list, and return the reversed list.
Example 1:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
Example 2:
Input: head = [1,2]
Output: [2,1]
*/
/*
APPROACH:
To reverse a singly linked list, we can use an iterative approach.
Initialize three pointers: prev as NULL, curr as head, and frwd as NULL.
Iterate through the linked list until curr becomes NULL:
- Store the next node of curr in frwd.
- Set the next of curr to prev, reversing the link.
- Move prev and curr one step forward.
- Move curr to the next node (frwd) to continue the iteration.
Return prev, which will be the new head of the reversed list.
*/
// CODE:-
ListNode* reverseList(ListNode* head) {
ListNode* prev = NULL;
ListNode* curr = head;
while (curr) {
ListNode* frwd = curr->next;
curr->next = prev;
prev = curr;
curr = frwd;
}
return prev;
}
// TIME COMPLEXITY: O(N)
// SPACE COMPLEXITY: O(1)
/*
QUESTION:-
Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.
Return true if there is a cycle in the linked list. Otherwise, return false.
Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).
Example 2:
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.
*/
/*
APPROACH:
To determine if a linked list has a cycle, we can use the two-pointer technique.
Initialize two pointers, slow and fast, to the head of the linked list.
Move the slow pointer one step at a time and the fast pointer two steps at a time.
If the linked list has a cycle, the fast pointer will eventually catch up to the slow pointer.
In other words, if there is a cycle, the two pointers will meet at some point.
If the fast pointer reaches the end of the list (i.e., it becomes NULL or reaches a node with a NULL next pointer), then there is no cycle in the linked list.
Return true if the two pointers meet (indicating a cycle), and false otherwise.
*/
// CODE:-
bool hasCycle(ListNode *head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
return true;
}
return false;
}
// TIME COMPLEXITY: O(N)
// SPACE COMPLEXITY: O(1)
/*
QUESTION:-
Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.
Do not modify the linked list.
Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.
Example 2:
Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.
*/
/*
APPROACH:
To find the node where the cycle begins in a linked list, we can use the Floyd's cycle-finding algorithm, also known as the "tortoise and hare" algorithm.
Initialize two pointers, slow and fast, to the head of the linked list.
Move the slow pointer one step at a time and the fast pointer two steps at a time.
If the linked list has a cycle, the fast pointer will eventually catch up to the slow pointer.
In other words, if there is a cycle, the two pointers will meet at some point.
Once the two pointers meet, move one of the pointers back to the head of the linked list.
Then, move both pointers one step at a time until they meet again.
The point at which they meet is the node where the cycle begins.
Return this node.
If the fast pointer reaches the end of the list (i.e., it becomes NULL or reaches a node with a NULL next pointer), then there is no cycle in the linked list, and we can return NULL.
*/
ListNode* startOfCycle(ListNode* slow, ListNode* fast) {
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
ListNode* detectCycle(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
fast = head;
return startOfCycle(slow, fast);
}
}
return NULL;
}
// TIME COMPLEXITY: O(N)
// SPACE COMPLEXITY: O(1)
/*
QUESTION:-
Given a linked list of size N. The task is to complete the function countNodesinLoop() that checks whether a given Linked List contains a loop or not and if the loop is present then return the count of nodes in a loop or else return 0. C is the position of the node to which the last node is connected. If it is 0 then no loop.
Example 1:
Input: N = 10
value[]={25,14,19,33,10,21,39,90,58,45}
C = 4
Output: 7
Explanation: The loop is 45->33. So
length of loop is 33->10->21->39->
90->58->45 = 7. The number 33 is
connected to the last node to form the
loop because according to the input the
4th node from the beginning(1 based
index) will be connected to the last
node for the loop.
Example 2:
Input: N = 2
value[] = {1,0}
C = 1
Output: 2
Explanation: The length of the loop
is 2.
*/
/*
APPROACH:
To detect a loop in a linked list, we can use the Floyd's cycle-finding algorithm, also known as the "tortoise and hare" algorithm.
Initialize two pointers, slow and fast, to the head of the linked list.
Move the slow pointer one step at a time and the fast pointer two steps at a time.
If the linked list has a loop, the fast pointer will eventually catch up to the slow pointer.
In other words, if there is a loop, the two pointers will meet at some point.
Once the two pointers meet, move one of the pointers back to the meeting point and start counting the number of nodes in the loop.
Continue moving the pointer until it reaches the meeting point again, counting the nodes along the way.
Return the count of nodes in the loop.
If the fast pointer reaches the end of the list (i.e., it becomes NULL or reaches a node with a NULL next pointer), then there is no loop in the linked list, and we can return 0.
*/
int countNode(struct Node* slow, struct Node* fast) {
int cnt = 1;
slow = slow->next;
while (fast != slow) {
slow = slow->next;
cnt++;
}
return cnt;
}
int countNodesinLoop(struct Node* head) {
struct Node* slow = head;
struct Node* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (fast == slow)
return countNode(slow, fast);
}
return 0;
}
// TIME COMPLEXITY: O(N)
// SPACE COMPLEXITY: O(1)
/*
QUESTION:-
Given the head of a singly linked list, return true if it is a palindrome or false otherwise.
Example 1:
Input: head = [1,2,2,1]
Output: true
Example 2:
Input: head = [1,2]
Output: false
*/
/*
APPROACH:
To determine if a linked list is a palindrome, we can follow these steps:
1. Find the middle node of the linked list using the slow and fast pointer technique.
2. Reverse the second half of the linked list.
3. Compare the first half of the original linked list with the reversed second half.
4. If all nodes match, the linked list is a palindrome.
5. If any node does not match, the linked list is not a palindrome.
*/
ListNode* reverseLL(ListNode* start) {
ListNode* prev = NULL;
ListNode* curr = start;
while (curr) {
ListNode* frwd = curr->next;
curr->next = prev;
prev = curr;
curr = frwd;
}
return prev;
}
bool isPalindrome(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
// Find the middle node using the slow and fast pointer technique
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
// Reverse the second half of the linked list
ListNode* reversedHalf = reverseLL(slow);
// Compare the first half with the reversed second half
while (reversedHalf) {
if (head->val != reversedHalf->val)
return false;
head = head->next;
reversedHalf = reversedHalf->next;
}
return true;
}
// TIME COMPLEXITY: O(N)
// SPACE COMPLEXITY: O(1)
/*
QUESTION:-
Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.
Example 1:
Input: head = [1,2,3,4,5]
Output: [1,3,5,2,4]
Example 2:
Input: head = [2,1,3,5,6,4,7]
Output: [2,3,6,7,1,5,4]
*/
/*
APPROACH:
To group nodes with odd indices together followed by nodes with even indices, we can follow these steps:
1. Initialize two pointers, `odd` and `even`, to the first and second nodes respectively.
2. Save the starting node of the even list as `evenHead`.
3. Iterate while `odd->next` and `even` are not NULL.
4. Connect the odd list with the next odd node (`odd->next = even->next`).
5. Move the `odd` pointer to the next odd node (`odd = odd->next`).
6. Connect the even list with the next even node (`even->next = odd->next`).
7. Move the `even` pointer to the next even node (`even = even->next`).
8. Connect the end of the odd list with the starting node of the even list (`odd->next = evenHead`).
9. Return the head of the modified list.
This approach reorders the linked list in place without using any extra space.
TIME COMPLEXITY: O(N)
SPACE COMPLEXITY: O(1)
*/
ListNode* oddEvenList(ListNode* head) {
if (!head || !head->next)
return head;
ListNode* odd = head;
ListNode* even = head->next;
ListNode* evenHead = even; // save the starting node of the even list
while (odd->next && even) {
odd->next = even->next; // connect the odd list with the next odd node
if (odd->next){
even->next = odd->next->next; // connect the even list with the next even node
odd = odd->next; // move the odd pointer to the next odd node
}
even = even->next; // move the even pointer to the next even node
}
odd->next = evenHead; // connect the end of the odd list with the starting node of the even list
return head;
}
/*
QUESTION:-
Given the head of a linked list, remove the nth node from the end of the list and return its head.
Example 1:
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
Example 2:
Input: head = [1], n = 1
Output: []
Example 3:
Input: head = [1,2], n = 1
Output: [1]
*/
/*
APPROACH:
To remove the nth node from the end of the linked list, we can follow these steps:
1. Initialize two pointers, `left` and `right`, to the head of the linked list.
2. Move the `right` pointer n nodes ahead.
3. If `right` becomes NULL, it means the first node needs to be removed. Return head->next.
4. Iterate until `right->next` becomes NULL.
5. Move both `left` and `right` pointers one node ahead in each iteration.
6. Once `right->next` becomes NULL, `left` will be pointing to the (n-1)th node from the end.
7. Update `left->next` to skip the nth node from the end.
8. Return the head of the modified linked list.
TIME COMPLEXITY: O(N)
SPACE COMPLEXITY: O(1)
*/
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* left = head;
ListNode* right = head;
// Move the right pointer n nodes ahead
for (int i = 0; i < n; i++) {
right = right->next;
}
// If right becomes NULL, remove the first node
if (!right)
return head->next;
// Iterate until right->next becomes NULL
while (right->next) {
left = left->next;
right = right->next;
}
// Update left->next to skip the nth node from the end
left->next = left->next->next;
return head;
}
/*
QUESTION:-
You are given the head of a linked list. Delete the middle node, and return the head of the modified linked list.
Example:
Input: head = [1,3,4,7,1,2,6]
Output: [1,3,4,1,2,6]
Explanation:
The above figure represents the given linked list. The indices of the nodes are written below.
Since n = 7, node 3 with value 7 is the middle node, which is marked in red.
We return the new list after removing this node.
APPROACH:
To delete the middle node of a linked list, we can use the slow and fast pointer technique.
1. Initialize three pointers: slow, fast, and prev.
2. Move the slow pointer one step at a time and the fast pointer two steps at a time.
3. Keep track of the previous node using the prev pointer.
4. When the fast pointer reaches the end of the linked list, the slow pointer will be at the middle node.
5. Update the next pointer of the previous node to skip the middle node.
6. Return the head of the modified linked list.
TIME COMPLEXITY: O(N)
SPACE COMPLEXITY: O(1)
*/
ListNode* deleteMiddle(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
ListNode* prev = NULL;
// Move the slow and fast pointers
while (fast && fast->next) {
prev = slow;
slow = slow->next;
fast = fast->next->next;
}
// Update the next pointer of the previous node
prev->next = slow->next;
return head;
}
/*
QUESTION:-
Given the head of a linked list, return the list after sorting it in ascending order.
Example:
Input: head = [4,2,1,3]
Output: [1,2,3,4]
APPROACH:
To sort a linked list, we can use the merge sort algorithm.
1. Implement a function to merge two sorted linked lists.
2. Implement a function to recursively divide the linked list into two halves.
3. Apply merge sort on each half.
4. Merge the sorted halves using the merge function.
5. Return the head of the sorted linked list.
TIME COMPLEXITY: O(NlogN)
SPACE COMPLEXITY: O(logN) - Recursive stack space
*/
ListNode* merge(ListNode* left, ListNode* right) {
if (left == NULL)
return right;
if (right == NULL)
return left;
if (left->val < right->val) {
left->next = merge(left->next, right);
return left;
} else {
right->next = merge(left, right->next);
return right;
}
}
ListNode* mergeSort(ListNode* start) {
if (start == NULL || start->next == NULL)
return start;
ListNode* slow = start;
ListNode* fast = start->next;
// Find the middle of the linked list
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
ListNode* a = mergeSort(slow->next); // Sort the right half
slow->next = NULL; // Break the linked list into two halves
ListNode* b = mergeSort(start); // Sort the left half
return merge(a, b); // Merge the sorted halves
}
ListNode* sortList(ListNode* head) {
return mergeSort(head);
}
/*
QUESTION:-
Given a linked list of N nodes where nodes can contain values 0s, 1s, and 2s only.
The task is to segregate 0s, 1s, and 2s in the linked list such that all zeros segregate to the head side, 2s at the end of the linked list, and 1s in the middle of 0s and 2s.
Example:
Input:
N = 8
value[] = {1,2,2,1,2,0,2,2}
Output: 0 1 1 2 2 2 2 2
Explanation: All the 0s are segregated to the left end of the linked list, 2s to the right end of the list, and 1s in between.
APPROACH:
Count the number of 0s, 1s, and 2s in the linked list.
Traverse the linked list and overwrite the nodes with 0s, 1s, and 2s based on their counts.
TIME COMPLEXITY: O(N)
SPACE COMPLEXITY: O(1)
*/
Node* segregate(Node* head) {
int zeroCnt = 0, oneCnt = 0, twoCnt = 0;
Node* curr = head;
// Count the number of 0s, 1s, and 2s in the linked list
while (curr) {
if (curr->data == 0) zeroCnt++;
if (curr->data == 1) oneCnt++;
if (curr->data == 2) twoCnt++;
curr = curr->next;
}
curr = head;
// Overwrite the nodes with 0s, 1s, and 2s based on their counts
while (zeroCnt) {
curr->data = 0;
zeroCnt--;
curr = curr->next;
}
while (oneCnt) {
curr->data = 1;
oneCnt--;
curr = curr->next;
}
while (twoCnt) {
curr->data = 2;
twoCnt--;
curr = curr->next;
}
return head;
}
/*
QUESTION:-
A number N is represented in a linked list such that each digit corresponds to a node in the linked list.
You need to add 1 to the number represented by the linked list.
APPROACH:
To add 1 to the number represented by the linked list, we can reverse the linked list, perform the addition, and then reverse it back.
First, reverse the linked list.
Traverse the reversed linked list while keeping track of the carry.
Add 1 to the least significant digit (head) and update the carry if necessary.
Continue traversing the linked list, adding the carry to each digit and updating the carry.
If there is still a remaining carry after traversing the linked list, create a new node with the carry as its value and append it to the end of the linked list.
Reverse the linked list again to restore its original order.
TIME COMPLEXITY: O(N), where N is the length of the linked list.
SPACE COMPLEXITY: O(1)
*/
Node* reverseLL(Node* head) {
Node* prev = NULL;
Node* curr = head;
while (curr) {
Node* frwd = curr->next;
curr->next = prev;
prev = curr;
curr = frwd;
}
return prev;
}
Node* addOne(Node* head) {
head = reverseLL(head);
Node* curr = head;
int carry = 1;
Node* last;
while (curr) {
long sum = curr->data + carry;
curr->data = sum % 10;
carry = sum / 10;
if (curr && !curr->next)
last = curr;
curr = curr->next;
}
while (carry) {
last->next = new Node(carry % 10);
carry = carry / 10;
last = last->next;
}
head = reverseLL(head);
return head;
}
/*
QUESTION:-
You are given two non-empty linked lists representing two non-negative integers.
The digits are stored in reverse order, and each of their nodes contains a single digit.
Add the two numbers and return the sum as a linked list.
APPROACH:
Traverse both linked lists simultaneously, starting from the heads.
At each step, add the corresponding digits from both linked lists along with the carry (initialized as 0).
Create a new node with the sum%10 and update the carry as sum/10.
Move to the next nodes in both linked lists.
Continue this process until both linked lists are traversed completely and there is no carry left.
If one linked list is shorter than the other, consider its remaining digits as 0.
If there is still a remaining carry, create a new node with the carry and append it to the result linked list.
Return the head of the result linked list.
TIME COMPLEXITY: O(max(N, M)), where N and M are the lengths of the two input linked lists.
SPACE COMPLEXITY: O(max(N, M)), as the length of the result linked list can be at most max(N, M)+1.
*/
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* p1 = l1;
ListNode* p2 = l2;
ListNode* dummy = new ListNode(); // Dummy node to simplify the logic
ListNode* ans = dummy;
int sum = 0, carry = 0;
while (p1 || p2) {
sum += carry; // Add the carry from the previous step
if (p1) {
sum += p1->val;
p1 = p1->next;
}
if (p2) {
sum += p2->val;
p2 = p2->next;
}
ans->next = new ListNode(sum % 10); // Create a new node with the current digit
carry = sum / 10; // Update the carry for the next step
sum = 0;
ans = ans->next; // Move to the next node in the result linked list
}
if (carry) {
ans->next = new ListNode(carry); // Append the remaining carry as a new node
}
return dummy->next; // Return the head of the result linked list (excluding the dummy node)
}
Medium Problems (Doubly Linked List)¶
/**QUESTION:**
You are given the head of a doubly Linked List and a key. Your task is to delete all occurrences of the given key and return the new doubly Linked List.
**Example:**
Input:
2 <-> 2 <-> 10 <-> 8 <-> 4 <-> 2 <-> 5 <-> 2
Key: 2
Output:
10 <-> 8 <-> 4 <-> 5
Explanation:
All occurrences of 2 have been deleted.
**APPROACH:**
To delete all occurrences of the given key from a doubly linked list, we can traverse the list and check each node's data. If the data matches the key, we handle three cases: deleting the first node, deleting the last node, and deleting a middle node. We update the pointers accordingly to remove the node from the list.
**TIME COMPLEXITY:** The time complexity is O(N), where N is the number of nodes in the doubly linked list.
**SPACE COMPLEXITY:** The space complexity is O(1) since we are modifying the given linked list in-place without using any extra space.
**CODE:**/
void deleteAllOccurOfX(struct Node** head_ref, int x) {
Node* curr = *head_ref;
while (curr) {
if (curr->data == x) {
// First node
if (!curr->prev) {
*head_ref = curr->next;
}
// Last node
else if (!curr->next) {
curr->prev->next = curr->next;
}
// Middle node
else {
curr->next->prev = curr->prev;
curr->prev->next = curr->next;
}
}
curr = curr->next;
}
}
/*
Given a sorted doubly linked list of positive distinct elements, the task is to find pairs in the doubly linked list whose sum is equal to a given value `target`.
Example 1:
Input:
1 <-> 2 <-> 4 <-> 5 <-> 6 <-> 8 <-> 9
Target: 7
Output: (1, 6), (2, 5)
Explanation: We can see that there are two pairs (1, 6) and (2, 5) with a sum of 7.
Example 2:
Input:
1 <-> 5 <-> 6
Target: 6
Output: (1, 5)
Explanation: We can see that there is one pair (1, 5) with a sum of 6.
Approach:
1. Initialize two pointers, `start` and `end`, pointing to the beginning and end of the doubly linked list, respectively.
2. While the `start` pointer's data is less than the `end` pointer's data:
- Calculate the sum of the data at the `start` and `end` pointers.
- If the sum is equal to the target value, add the pair (start->data, end->data) to the result vector and move both the `start` and `end` pointers.
- If the sum is less than the target value, move the `start` pointer to the next node.
- If the sum is greater than the target value, move the `end` pointer to the previous node.
3. Return the result vector containing all the pairs whose sum is equal to the target.
Time Complexity: O(N), where N is the number of nodes in the doubly linked list.
Space Complexity: O(1).
CODE:
*/
vector<pair<int, int>> findPairsWithGivenSum(Node *head, int target)
{
vector<pair<int, int>> ans;
Node* start = head;
Node* end = head;
while (end->next) {
end = end->next;
}
while (start->data < end->data) {
int sum = start->data + end->data;
if (sum == target) {
ans.push_back({ start->data, end->data });
start = start->next;
end = end->prev;
}
else if (sum < target) {
start = start->next;
}
else {
end = end->prev;
}
}
return ans;
}
/*Given a doubly linked list of n nodes sorted by values, the task is to remove duplicate nodes present in the linked list.
Example 1:
Input:
n = 6
1<->1<->1<->2<->3<->4
Output:
1<->2<->3<->4
Explanation:
Only the first occurrence of the node with value 1 is retained, and the rest of the nodes with value 1 are deleted.
Example 2:
Input:
n = 7
1<->2<->2<->3<->3<->4<->4
Output:
1<->2<->3<->4
Explanation:
Only the first occurrence of nodes with values 2, 3, and 4 are retained, and the rest of the repeating nodes are deleted.
Approach:
1. Initialize a variable `dupli` with the value of the head node.
2. Start from the next node, `curr`, and iterate until the end of the linked list.
3. For each node, check if its data is equal to `dupli`.
- If it is equal, remove the node by updating the `next` and `prev` pointers of its neighboring nodes.
- Continue removing all consecutive nodes with the same value.
4. If `curr` is not null, update `dupli` with the data of `curr`.
5. Repeat steps 3-4 until the end of the linked list is reached.
6. Return the head of the modified linked list.
Time Complexity: O(N), where N is the number of nodes in the linked list.
Space Complexity: O(1).
CODE:
*/
Node* removeDuplicates(Node* head)
{
int dupli = head->data;
Node* curr = head->next;
while (curr) {
while (curr && curr->data == dupli) {
if (curr->next)
curr->next->prev = curr->prev;
curr->prev->next = curr->next;
curr = curr->next;
}
if (curr) {
dupli = curr->data;
curr = curr->next;
}
}
return head;
}
Hard Problems (Linked List)¶
/*
QUESTION:-
Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.
APPROACH:
The idea is to reverse the nodes of the linked list in groups of size k.
First, we need to check if there are at least k nodes remaining in the linked list. If not, we return the head as it is.
Next, we reverse the first k nodes of the linked list. To do this, we maintain three pointers: prev, curr, and frwd.
We iterate through the first k nodes and at each step, we reverse the links between the nodes.
After reversing the first k nodes, prev becomes the new head, and curr becomes the new tail of the reversed group.
We recursively call the function on the remaining linked list starting from frwd (which points to the (k+1)-th node).
Finally, we update the next pointer of the original head to point to the reversed group obtained from the recursive call.
TIME COMPLEXITY: O(N), where N is the number of nodes in the linked list.
SPACE COMPLEXITY: O(1).
*/
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode* ptr = head;
for (int i = 0; i < k; i++) {
if (!ptr)
return head; // Return head if there are less than k nodes remaining
ptr = ptr->next;
}
int count = k;
ListNode* prev = NULL;
ListNode* curr = head;
ListNode* frwd = NULL;
while (count && curr) {
frwd = curr->next;
curr->next = prev;
prev = curr;
curr = frwd;
count--;
}
if (frwd)
head->next = reverseKGroup(frwd, k); // Recursive call for the remaining linked list
return prev; // Return the new head of the reversed group
}
/*
QUESTION:-
Given the head of a linked list, rotate the list to the right by k places.
APPROACH:
To rotate the linked list to the right by k places, we need to perform the following steps:
1. Find the length of the linked list and connect the last node to the head to form a circular linked list.
2. Calculate the actual number of rotations by taking the modulus of k with the length of the linked list.
3. Traverse to the (length - k - 1)th node, which will be the new tail of the rotated list.
4. Set the new head as the next node of the (length - k - 1)th node and disconnect it from the rest of the list.
5. Return the new head.
TIME COMPLEXITY: O(N), where N is the number of nodes in the linked list.
SPACE COMPLEXITY: O(1).
*/
int find_len(ListNode* head) {
ListNode* curr = head;
int cnt = 1;
while (curr->next) {
curr = curr->next;
cnt++;
}
curr->next = head; // Connect the last node to the head to form a circular linked list
return cnt;
}
ListNode* rotateRight(ListNode* head, int k) {
if (head == NULL || k == 0)
return head;
int len = find_len(head); // Find the length of the linked list and form a circular linked list
k = k % len; // Calculate the actual number of rotations
ListNode* curr = head;
// Traverse to the (length - k - 1)th node
for (int i = 0; i < len - k - 1; i++) {
curr = curr->next;
}
ListNode* newHead = curr->next; // The next node will be the new head
curr->next = NULL; // Disconnect the new tail from the rest of the list
return newHead;
}
/*
QUESTION:
A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.
Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.
For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y.
Return the head of the copied linked list.
The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:
val: an integer representing Node.val
random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.
Your code will only be given the head of the original linked list.
Example 1:
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]
Example 2:
Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]
APPROACH:
To create a deep copy of a linked list with random pointers, we can follow these steps:
1. Traverse the original linked list and create a new node for each node in the original list. Insert the new node between the original node and its next node.
2. Set the random pointer of the new node by mapping it to the corresponding random node in the original list.
3. Separate the original list and the copied list by updating the next pointers of nodes in both lists.
4. Return the head of the copied list.
TIME COMPLEXITY:
The time complexity of this approach is O(n) since we traverse the original list once to create the copied list.
SPACE COMPLEXITY:
The space complexity is also O(n) because we create a new node for each node in the original list.
CODE:
*/
Node* copyRandomList(Node* head) {
if (head == NULL)
return head;
// inserting dupli node in between
Node* orig = head;
while (orig) {
Node* temp = orig->next;
orig->next = new Node(orig->val);
orig->next->next = temp;
orig = orig->next->next;
}
// setting random pointers
orig = head;
while (orig) {
if (orig->random && orig->next)
orig->next->random = orig->random->next;
orig = orig->next->next;
}
// setting next pointers and dettaching duplicate nodes from the original list
orig = head;
Node* ans = orig->next;
while (orig && orig->next) {
Node* temp = orig->next->next;
if (orig->next->next)
orig->next->next = orig->next->next->next;
orig->next = temp;
orig = orig->next;
}
return ans;
}
/**QUESTION:**
Given a Linked List of size N, where every node represents a sub-linked-list and contains two pointers:
(i) a next pointer to the next node,
(ii) a bottom pointer to a linked list where this node is the head.
Each of the sub-linked lists is in sorted order.
Flatten the Link List such that all the nodes appear in a single level while maintaining the sorted order.
Note: The flattened list will be printed using the bottom pointer instead of the next pointer.
**APPROACH:**
To flatten the linked list, we can use a recursive approach. The idea is to flatten the list from right to left. Starting from the last node, we recursively flatten the sublist pointed by the bottom pointer and merge it with the current node. We continue this process until we reach the head of the original linked list. Finally, we return the flattened list.
**TIME COMPLEXITY:** The time complexity is O(N), where N is the total number of nodes in the linked list.
**SPACE COMPLEXITY:** The space complexity is O(1) since we are modifying the given linked list in-place without using any extra space.
**CODE:**/
Node* merge(Node* head1, Node* head2)
{
if (head1 == NULL)
return head2;
if (head2 == NULL)
return head1;
if (head1->data < head2->data) {
head1->bottom = merge(head1->bottom, head2);
return head1;
}
else {
head2->bottom = merge(head1, head2->bottom);
return head2;
}
}
Node* flatten(Node* root)
{
if (root == NULL)
return root;
Node* left = root;
Node* right = flatten(root->next);
root->next = NULL;
left = merge(left, right);
return left;
}