1
Pranveer Singh Institute of Technology
Name: Deepansh Pal
Branch: Compute Science and Engineering
Subject: Data Structure and Algorithm
Student Id: 2412163
Linked List Question
1. Detect a loop in a linked list
Ans. Code:
int hasCycle(Node* head) {
Node *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return 1;
}
return 0;
}
2. Add “1” to a number represented by a linked list
Ans. Codes:
Node* reverse(Node* head) {
2
Node *prev = NULL, *next = NULL;
while (head) {
next = head->next;
head->next = prev;
prev = head;
head = next;
}
return prev;
}
Node* addOne(Node* head) {
head = reverse(head);
Node *current = head;
int carry = 1;
while (current && carry) {
current->data += carry;
carry = current->data / 10;
current->data %= 10;
if (!current->next && carry) {
current->next =
(Node*)malloc(sizeof(Node));
current->next->data = 0;
current->next->next = NULL;
}
current = current->next;
}
3
return reverse(head);
}
3. Reverse a portion of the linked list between two
position
Ans. Codes:
Node* reverseBetween(Node* head, int low, int
high) {
Node dummy;
[Link] = head;
Node* prev = &dummy;
for (int i = 1; i < low; i++) {
prev = prev->next;
}
Node* reverse_start = prev->next;
Node* then = reverse_start->next;
for (int i = 0; i < high - low; i++) {
reverse_start->next = then->next;
then->next = prev->next;
prev->next = then;
then = reverse_start->next;
}
4
return [Link];
}
4. Remove a loop from a linked list
Ans. Codes:
void removeLoop(Node* head) {
Node *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) break;
}
if (slow != fast) return;
slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
while (fast->next != slow) {
fast = fast->next;
}
5
fast->next = NULL;
}
5. Find the intersection of two sorted linked list
Ans. Codes:
Node* getIntersection(Node* head1, Node* head2) {
Node dummy;
Node* tail = &dummy;
while (head1 && head2) {
if (head1->data == head2->data) {
tail->next = (Node*)malloc(sizeof(Node));
tail = tail->next;
tail->data = head1->data;
head1 = head1->next;
head2 = head2->next;
} else if (head1->data < head2->data) {
head1 = head1->next;
} else {
head2 = head2->next;
}
}
6
tail->next = NULL;
return [Link];
}
6. Merge two sorted linked lists
Ans. Codes:
Node* mergeSortedLists(Node* l1, Node* l2) {
Node dummy;
Node* tail = &dummy;
while (l1 && l2) {
if (l1->data < l2->data) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
tail->next = l1 ? l1 : l2;
return [Link];
7
}
7. Detect and remove duplicates from a linked list
Ans. Codes:
void removeDuplicates(Node* head) {
Node* current = head;
while (current && current->next) {
if (current->data == current->next->data) {
Node* temp = current->next;
current->next = current->next->next;
free(temp);
} else {
current = current->next;
}
}
}
8. Find the middle element of a linked list
Ans. Codes:
int findMiddle(Node* head) {
Node *slow = head, *fast = head;
while (fast && fast->next) {
8
slow = slow->next;
fast = fast->next->next;
}
return slow->data;
}
9. Reverse a linked list
Ans. Codes:
Node* reverseList(Node* head) {
Node *prev = NULL, *next = NULL;
while (head) {
next = head->next;
head->next = prev;
prev = head;
head = next;
}
return prev;
}
[Link] a linked List
Ans. Codes:
Node* rotateList(Node* head, int k) {
9
if (!head) return NULL;
Node *old_tail = head, *new_head = head;
int length = 1;
while (old_tail->next) {
old_tail = old_tail->next;
length++;
}
old_tail->next = head;
for (int i = 0; i < length - k % length - 1; i++) {
new_head = new_head->next;
}
Node* new_tail = new_head;
new_head = new_head->next;
new_tail->next = NULL;
return new_head;
}
[Link] the nth node from the end of a linked list
Ans. Codes:
int nthFromEnd(Node* head, int n) {
Node *fast = head, *slow = head;
for (int i = 0; i < n; i++) {
10
if (fast == NULL) return -1; // n is larger than
the list length
fast = fast->next;
}
while (fast) {
slow = slow->next;
fast = fast->next;
}
return slow->data;
}
[Link] if a linked list in palindrome
Ans. Codes:
int isPalindrome(Node* head) {
Node *slow = head, *fast = head, *second_half,
*prev_of_slow = head;
Node *midnode = NULL;
int res = 1;
if (head && head->next) {
while (fast && fast->next) {
fast = fast->next->next;
prev_of_slow = slow;
slow = slow->next;
}
if (fast) {
midnode = slow;
11
slow = slow->next;
}
second_half = reverse(slow);
res = compareLists(head, second_half);
second_half = reverse(second_half);
if (midnode) {
prev_of_slow->next = midnode;
midnode->next = second_half;
} else {
prev_of_slow->next = second_half;
}
}
return res;
}
13. Split a linked list into two halves
Ans. Codes:
void splitList(Node* head, Node** first_half,
Node** second_half) {
Node *slow = head, *fast = head;
if (!head || !head->next) {
*first_half = head;
*second_half = NULL;
} else {
while (fast && fast->next) {
fast = fast->next->next;
if (fast) slow = slow->next;
12
}
*first_half = head;
*second_half = slow->next;
slow->next = NULL;
}
}
13
14