1.
Write a function to detect if a linked list
has a loop, and return the node where the loop starts.
In this code, we use two pointers, slow and fast, to
traverse the linked list. The slow pointer moves one node at a time, while the
fast pointer moves two nodes at a time. If the linked list has a loop, the slow
and fast pointers will eventually meet at some node in the loop. We then use
two additional pointers, ptr1 and ptr2, to find the node where the loop starts.
ptr1 starts from the head of the linked list and ptr2 starts from the node
where slow and fast meet. We move both pointers one node at a time until they
meet at the starting node of the loop. Finally, we return this node.
struct Node {
int val;
Node* next;
Node(int val) : val(val), next(nullptr) {}
};
Node*
DetectLoop(Node* head) {
Node* slow = head;
Node* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
Node* ptr1 = head;
Node* ptr2 = slow;
while (ptr1 != ptr2) {
ptr1 = ptr1->next;
ptr2 = ptr2->next;
}
return ptr1;
}
}
return nullptr;
}
2.
Write a function to find the intersection
point of two linked lists, if any.
In
this code, we first calculate the length of both linked lists. We then traverse
the longer linked list until both linked lists have the same length. Finally,
we traverse both linked lists simultaneously until we find the node where they
intersect, or return nullptr if they do not intersect.
The
time complexity of the code I provided to find the intersection point of two
linked lists is O(m+n), where m and n are the lengths of the two linked lists.
This is because we traverse both linked lists once to calculate their lengths,
and then traverse the longer linked list to make it the same length as the
shorter one. Finally, we traverse both linked lists simultaneously until we
find the intersection point.
This
is an optimal solution in terms of time complexity since we have to traverse
both linked lists at least once to find the intersection point. However, we can
make a small optimization by calculating the lengths of the two linked lists in
a single pass instead of two separate passes. This would not improve the time
complexity of the algorithm, but it would reduce the number of iterations
required to find the intersection point.
struct Node {
int val;
Node* next;
Node(int val) : val(val), next(nullptr) {}
};
int length(Node*
head) {
int len = 0;
while (head) {
len++;
head = head->next;
}
return len;
}
Node*
getIntersectionNode(Node* headA, Node* headB) {
int lenA = length(headA);
int lenB = length(headB);
while (lenA > lenB) {
headA = headA->next;
lenA--;
}
while (lenB > lenA) {
headB = headB->next;
lenB--;
}
while (headA && headB) {
if (headA == headB) {
return headA;
}
headA = headA->next;
headB = headB->next;
}
return nullptr;
}
3.
Write a function to remove the nth node from
the end of a linked list, and return the head of the modified list.
#include
<iostream>
#include
<stdexcept>
using
namespace std;
struct
ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
/**
* Removes the nth node from the end of a
linked list.
*
* @param head The head of the linked list.
* @param n The position of the node to be
removed from the end of the list.
* @return The head of the modified list.
* @throws invalid_argument If the input n is
less than or equal to 0, or greater than the length of the list.
*/
ListNode*
removeNthFromEnd(ListNode* head, int n) {
if (n <= 0) {
throw invalid_argument("n should
be greater than 0");
}
// Calculate the length of the list
int len = 0;
ListNode *current = head;
while (current != NULL) {
len++;
current = current->next;
}
if (n > len) {
throw invalid_argument("n is
greater than the length of the list");
}
// Calculate the position of the node to be
removed
int pos = len - n;
// If the head node is to be removed
if (pos == 0) {
ListNode *temp = head;
head = head->next;
delete temp;
return head;
}
// Traverse the list to the node before the
node to be removed
ListNode *prev = NULL;
current = head;
for (int i = 0; i < pos; i++) {
prev = current;
current = current->next;
}
// Remove the node and update the links
prev->next = current->next;
delete current;
return head;
}
//
Function to print the linked list
void
printList(ListNode* head) {
ListNode *current = head;
while (current != NULL) {
cout << current->val <<
" ";
current = current->next;
}
cout << endl;
}
int
main() {
// Create a sample linked list
ListNode *head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);
head->next->next->next = new
ListNode(4);
head->next->next->next->next =
new ListNode(5);
cout << "Original list: ";
printList(head);
try {
// Remove the 2nd node from the end of
the list
head = removeNthFromEnd(head, 2);
cout << "Modified list:
";
printList(head);
// Remove the 5th node from the end of
the list
head = removeNthFromEnd(head, 5);
cout << "Modified list:
";
printList(head);
// Try to remove a node beyond the
length of the list
head = removeNthFromEnd(head, 10);
}
catch (const invalid_argument& e) {
cerr << "Error: "
<< e.what() << endl;
}
// Free the memory
while (head != NULL) {
ListNode *temp = head;
head = head->next;
delete temp;
}
return 0;
}
4.
Write a function to partition a linked list
around a given value x, such that all nodes less than x come before nodes
greater than or equal to x.
#include <iostream>
using namespace std;
// Definition for singly-linked list.
struct ListNode {
int val;
ListNode *next;
ListNode(int x)
: val(x), next(NULL) {}
};
/**
* Function to
partition a linked list around a given value x, such that all nodes less than x
* come before
nodes greater than or equal to x.
*
* @param head: The
head of the linked list to be partitioned
* @param x: The
value around which the linked list is to be partitioned
* @return: The
head of the modified linked list
*/
ListNode* partition(ListNode* head, int x) {
// Create two
dummy nodes, one for the nodes less than x and another for nodes greater than x
ListNode* less
= new ListNode(0);
ListNode*
greater = new ListNode(0);
// Create
pointers for traversing the original list and the two dummy lists
ListNode*
current = head;
ListNode*
lessCurrent = less;
ListNode*
greaterCurrent = greater;
// Traverse the
original list and insert nodes into the appropriate dummy lists
while (current
!= NULL) {
if
(current->val < x) {
lessCurrent->next = current;
lessCurrent = lessCurrent->next;
} else {
greaterCurrent->next = current;
greaterCurrent = greaterCurrent->next;
}
current =
current->next;
}
// Merge the
two dummy lists and return the head of the modified list
greaterCurrent->next = NULL;
lessCurrent->next = greater->next;
return
less->next;
}
/**
* Function to
print the values of a linked list
*
* @param head: The
head of the linked list to be printed
*/
void printList(ListNode* head) {
while (head !=
NULL) {
cout
<< head->val << " ";
head =
head->next;
}
cout << endl;
}
// Testing code
int main() {
// Test case 1
ListNode* head
= new ListNode(1);
head->next =
new ListNode(4);
head->next->next = new ListNode(3);
head->next->next->next = new ListNode(2);
head->next->next->next->next = new ListNode(5);
head->next->next->next->next->next = new ListNode(2);
int x = 3;
cout <<
"Original list: ";
printList(head);
head =
partition(head, x);
cout <<
"Modified list: ";
printList(head);
cout <<
endl;
// Test case 2
head = new
ListNode(2);
head->next =
new ListNode(1);
x = 2;
cout <<
"Original list: ";
printList(head);
head =
partition(head, x);
cout <<
"Modified list: ";
printList(head);
cout <<
endl;
// Test case 3
head = new
ListNode(1);
head->next =
new ListNode(2);
head->next->next = new ListNode(3);
head->next->next->next = new ListNode(4);
head->next->next->next->next = new ListNode(5);
head->next->next->next->next->next = new ListNode(6);
x = 0;
cout <<
"Original list: ";
printList(head);
head =
partition(head, x);
cout <<
"Modified list: ";
printList(head);
cout <<
endl
}
5.
Write a function to reverse a linked list in
groups of size k.
6.
Implement a function to add two numbers
represented by linked lists, where each node contains a single digit of the
number.
7.
Implement a function to merge k sorted linked
lists into one sorted linked list.
8.
Implement a function to sort a linked list
using the quicksort algorithm.
9.
Write a function to check if a given linked
list is a palindrome.
10. Implement
a function to clone a linked list with a random pointer, where each node has an
additional pointer that points to a random node in the list.
Note: The suggested order is based on the assumption that
the code from the previous problems can be reused to some extent for the
subsequent problems, but this may not always be the case depending on the
implementation approach.
Comments
Post a Comment