Question 1.
Middle of the Linked List
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.
Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3.
class Solution {
public:
ListNode* middleNode(ListNode* head) {
//bruth force approach
// First, count the number of nodes
ListNode* temp = head;
int cnt = 0;
while (temp != nullptr) {
cnt++;
temp = temp->next;
}
// Find the middle index (0-based index)
int middle = cnt / 2;
// Reset temp to head to traverse again
temp = head;
// Traverse to the middle node
for (int i = 0; i < middle; i++) {
temp = temp->next;
}
// Return the middle node
return temp;
}
};
Optimal Approach
Node *findMiddle(Node *head) {
// Initialize the slow pointer to the head.
Node *slow = head;
// Initialize the fast pointer to the head.
Node *fast = head;
// Traverse the linked list using the
// Tortoise and Hare algorithm.
while (fast != NULL && fast->next != NULL) {
// Move slow one step.
slow = slow->next;
// Move fast two steps.
fast = fast->next->next;
// Return the slow pointer,
// which is now at the middle node.
return slow;
}
Question 2. Given the head of a singly linked list, reverse the list, and return
the reversed list.
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
class Solution {
public:
ListNode* reverseList(ListNode* head) {
// stack<int>st;
// ListNode* temp=head;
// while(temp!=NULL){
// st.push(temp->val);
// temp=temp->next;
// }
// temp=head;
// while(temp!=NULL){
// temp->val = st.top();
// st.pop();
// temp=temp->next;
// }
// return head;
ListNode* prev=NULL;
ListNode* next=NULL;
ListNode* current=head;
while(current != nullptr){
next=current->next;
current->next = prev;
prev = current;
current = next;
}
return prev;
}
};
Question: Add Two Number
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* dummyHead = new ListNode(-1);
ListNode* curr = dummyHead;
ListNode* temp1=l1;
ListNode* temp2=l2;
int carry=0;
while(temp1 !=NULL || temp2 !=NULL){
int sum=carry;
if(temp1) sum+=temp1->val;
if(temp2) sum+=temp2->val;
ListNode* newNode = new ListNode(sum%10);
carry = sum/10;
curr->next = newNode;
curr = curr->next;
if(temp1) temp1=temp1->next;
if(temp2) temp2=temp2->next;
}
if(carry){
ListNode* newNode =new ListNode(carry);
curr->next = newNode;
}
return dummyHead->next;
}
};
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.
bool hasCycle(ListNode *head) {
//bruth force approach
// map<int,int>numbercount;
// ListNode* temp=head;
// while(temp!=NULL){
// numbercount[temp->val]++;
// temp=temp->next;
// }
// for(const auto& pair : numbercount){
// if (pair.second == 2) {
// return true;
// }
// }
// return false;
ListNode* slow=head;
ListNode* fast=head;
while(fast!=NULL&& fast->next!=NULL){
slow=slow->next;
fast=fast->next->next;
//at some point of time if there is cycle then they will meet at same point
if (slow == fast) {
return true; // Loop detected
}
}
return false;
}
Question Given the head of a linked list, determine whether the list contains
a loop. If a loop is present, return the number of nodes in the loop,
otherwise return 0.
class Solution {
public:
// Function to find the length of a loop in the linked list.
int countNodesinLoop(Node *head) {
// Code here
Node* slow=head;
Node* fast=head;
int count=0;
while(fast!=NULL && fast->next!=NULL){
slow=slow->next;
fast=fast->next->next;
if(slow == fast){
Node* temp=slow;
do{
temp=temp->next;
count++;
}while(temp!=slow);
return count;
}
return 0;
};
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.
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* slow = head;
ListNode* fast = head;
while(fast!=NULL && fast->next!=NULL){
slow=slow->next;
fast=fast->next->next;
if(slow==fast){
ListNode* start=head;
while(start !=slow){
start=start->next;
slow=slow->next;
return start;
return NULL;
}
};
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.
The first node is considered odd, and the second node is even, and so on.
Note that the relative order inside both the even and odd groups should
remain as it was in the input.
You must solve the problem in O(1) extra space complexity and O(n) time
complexity.
class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
if (head == NULL || head->next == NULL){
return head;
ListNode* odd=head;
ListNode* even=head->next;
ListNode* evenHead=head->next;
while(even!=NULL && even->next!=NULL){
odd->next=odd->next->next;
even->next = even->next->next;
odd=odd->next;
even=even->next;
odd->next=evenHead;
return head;
};
Question : Palindrome Linked List
Input: head = [1,2,2,1]
Output: true
class Solution {
ListNode* reverseLinkedList(ListNode* head){
if (head == NULL || head->next == NULL) {
return head;
ListNode* newHead = reverseLinkedList(head->next);
ListNode* front = head->next;
front->next = head;
head->next = NULL;
return newHead;
public:
bool isPalindrome(ListNode* head) {
if(head == NULL && head->next == NULL){
return true;
ListNode* slow=head;
ListNode* fast=head;
while(fast!=NULL && fast->next != NULL){
slow=slow->next;
fast=fast->next->next;
ListNode* newHead=reverseLinkedList(slow);
ListNode* first = head;
ListNode* second = newHead;
while(second != NULL){
if(first->val != second->val){
reverseLinkedList(newHead);
return false;
first=first->next;
second=second->next;
reverseLinkedList(newHead);
return true;
};
Question Remove Nth Node From End of List
Given the head of a linked list, remove the nth node from the end of the list
and return its head.
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* fast = head;
// Move fast n steps ahead
for(int i = 0; i < n; i++) {
fast = fast->next;
// If fast reaches NULL, it means we need to remove the head node
if(fast == NULL) {
return head->next;
ListNode* slow = head;
// Move fast and slow together until fast reaches the last node
while(fast->next != NULL) {
slow = slow->next;
fast = fast->next;
// Remove the nth node
ListNode* delNode = slow->next;
slow->next = slow->next->next;
// Deallocate the memory using delete instead of free
delete delNode;
return head;
};
Question: Sort List
Given the head of a linked list, return the list after sorting it in ascending order.
class Solution {
public:
ListNode* mergeTwoSortedLists(ListNode* list1,ListNode* list2){
ListNode* dummynode = new ListNode(-1);
ListNode* temp = dummynode;
while(list1 != nullptr && list2 != nullptr){
if(list1->val <= list2->val){
temp->next=list1;
list1=list1->next;
else{
temp->next=list2;
list2=list2->next;
temp=temp->next;
if(list1 != nullptr){
temp->next = list1;
else{
temp->next = list2;
return dummynode->next;
ListNode* findMiddle(ListNode* head){
if(head==nullptr || head->next==nullptr){
return head;
ListNode* slow=head;
ListNode* fast=head->next;
while(fast!=nullptr && fast->next !=nullptr){
slow=slow->next;
fast=fast->next->next;
return slow;
ListNode* sortList(ListNode* head) {
if(head==nullptr || head->next==nullptr){
return head;
ListNode* middle = findMiddle(head);
ListNode* right = middle->next;
ListNode* left=head;
middle->next = nullptr;
//recursively sort the left and right halves
left = sortList(left);
right = sortList(right);
return mergeTwoSortedLists(left,right);
}
};
Question Add 1 to a Linked List Number
class Solution {
Node* reverseLinkedlist(Node* head) {
if (head == NULL || head->next == NULL) {
return head;
Node* newHead = reverseLinkedlist(head->next);
Node* front = head->next;
front->next = head;
head->next = NULL;
return newHead;
public:
Node* addOne(Node* head) {
// Step 1: Reverse the linked list
head = reverseLinkedlist(head);
// Step 2: Add 1 to the reversed linked list
Node* temp = head;
int carry = 1; // Initialize carry as 1, because we are adding 1
while (temp != NULL) {
temp->data = temp->data + carry;
if (temp->data < 10) {
carry = 0; // No carry to propagate
break;
} else {
temp->data = 0; // Set current node to 0 and propagate the carry
carry = 1; // Continue to propagate carry
if (temp->next == NULL && carry == 1) {
// If it's the last node and there's still a carry, add a new node with value 1
temp->next = new Node(1);
carry = 0;
break;
temp = temp->next;
// Step 3: Reverse the list back to its original order
head = reverseLinkedlist(head);
return head;
};
