Detect Cycle in a Linked List in C++.

Given the head of a linked list, detect if the given linked list contains a cycle. Return true if there exists a cycle else return false. Below is an example of two linked lists containing cycles.

Approach 1: Using Hashmap.

In this approach, you are going to insert all the nodes one by one inside a hashmap, and whenever you found a condition that a particular node is already present in the hashmap then it means there exists a cycle so return true.

C++ Solution Code:

/*C++ Program detect cycle in a linked list using hashmap*/
#include<bits/stdc++.h>
using namespace std;

class ListNode{
    public:
      int data;
      ListNode *next;

    //constructor
    ListNode(int data){
        this->data = data;
        this->next = NULL;
    }  
};
//creating new node
ListNode *newNode(int data){
    ListNode *temp = new ListNode(data);
    temp->next = NULL;
    return temp;
}
//function to print linked list
void printList(ListNode *head){
    ListNode *temp = head;

    while(temp != NULL){
        cout<<temp->data<<" ";
        temp = temp->next;
    }
}
//Function to detect cycle of linked list
bool detectCycle(ListNode *head){
    unordered_set<ListNode*> hp;
    //loop to check cycle
    while(head != NULL){

        if(hp.find(head) != hp.end())
           return true;
        hp.insert(head);   
        head = head->next;   
    }
    return false;
}
int main(){

    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 = head; //cycle formation

    bool check = detectCycle(head);

    if(check)
      cout<<"Linked List contains a cycle.";
    else
      cout<<"Linked List does not contain a cycle.";

    return 0;
}

Output:

Linked List contains a cycle.

• Time Complexity: O(n) where n is the number of nodes present.
• Space Complexity: O(n) because we are using one extra hashmap.

Approach 2: Two Pointer Approach (Slow and Fast Pointer).

In this approach, you need to use two pointers and one pointer will move slower than the other pointer. If the linked list contains a cycle then slow and fast pointers must meet at some point and if they meet each other at any point it means there exists a cycle.

• Initialize two pointers, slow and fast with the head of the linked list.
• Traverse the list, every time the slow pointer moves one step, and the faster moves two steps
• If there is a cycle then both slow and fast pointers will meet at some point, return true if they meet else return false.

C++ Solution Code:

/*C++ Program detect cycle in a linked list using 
two pointer approach*/
#include<bits/stdc++.h>
using namespace std;

class ListNode{
    public:
      int data;
      ListNode *next;

    //constructor
    ListNode(int data){
        this->data = data;
        this->next = NULL;
    }  
};
//creating new node
ListNode *newNode(int data){
    ListNode *temp = new ListNode(data);
    temp->next = NULL;
    return temp;
}
//function to print linked list
void printList(ListNode *head){
    ListNode *temp = head;

    while(temp != NULL){
        cout<<temp->data<<" ";
        temp = temp->next;
    }
}
//Function to detect cycle of linked list
bool detectCycle(ListNode *head){
    
    if(head == NULL) return false;

    ListNode* slow = head;
    ListNode* fast = head;

    while(fast != NULL && fast->next != NULL){
        slow = slow->next;
        fast = fast->next->next;

        if(slow == fast) return true; //cycle detected
    }
    return false;
}
int main(){

    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 = head; //cycle formation

    bool check = detectCycle(head);

    if(check)
      cout<<"Linked List contains a cycle.";
    else
      cout<<"Linked List does not contain a cycle.";

    return 0;
}

Output:

Linked List contains a cycle.

• Time Complexity: O(n) where n is the number of nodes in the linked list.
• Space Complexity: O(1)

Related Articles:

• Convert Binary Linked List to Integer.

• Find the Middle of the Singly Linked List in C++.

• Reverse a Singly Linked List in C++.

• Merge Two Sorted Linked List in C++.

• Intersection Point of Two Linked Lists in C++.

Intersection Point of Two Linked Lists in C++.

Given head nodes of two singly Linked List. Somehow, both the linked lists intersected at one point and we need to return the intersection of those two linked lists. If there is no intersection point between two linked lists then you can return a NULL. 

Note: There is no circle present in the structure of two linked lists and you are not allowed to make any changes to the original structure of the linked list. (alert-passed)

Approach 1: Brute Force (using two nested loops).

Run two nested loops where the outer loop is for the first list and the inner loop is for the second list. You need to check that for at least one current node of the first list there exists one same node that is present in the second list. The time complexity of this algorithm is O(m*n) where m and n are the numbers of nodes present in both lists.

C++ Solution Code:

/*C++ Program to find Intersection of Two Linked List*/
#include<bits/stdc++.h>
using namespace std;

class ListNode{
    public:
      int data;
      ListNode *next;

    //constructor
    ListNode(int data){
        this->data = data;
        this->next = NULL;
    }  
};
//creating new node
ListNode *newNode(int data){
    ListNode *temp = new ListNode(data);
    temp->next = NULL;
    return temp;
}

//function to print linked list
void printList(ListNode *head){
    ListNode *temp = head;

    while(temp != NULL){
        cout<<temp->data<<" ";
        temp = temp->next;
    }
}
//Function to find intersection of two linked list
ListNode *findIntersection(ListNode *head1, ListNode *head2){

    while(head2){
        ListNode *temp = head1;
        while(temp){
            if(temp == head2)
              return head2;
            temp = temp->next;  
        }
        head2 = head2->next;
    }
    return NULL;
}
int main(){
    /*
    1st Linked List: 4->1->5->3->4
    2nd Linked List: 5->2->1->5->3->4
    Both are intersecting at 5
    */
    ListNode *head1 = new ListNode(4);
    head1->next = new ListNode(1);
    ListNode *commonNode;
    commonNode = new ListNode(5);
    commonNode->next = new ListNode(3);
    commonNode->next->next = new ListNode(4);
    head1->next->next = commonNode;

    ListNode *head2 = new ListNode(5);
    head2->next = new ListNode(2);
    head2->next->next = new ListNode(1);
    head2->next->next->next = commonNode;

    cout<<"Linked List1: ";
    printList(head1);

    cout<<"\nLinked List2: ";
    printList(head2);

    ListNode *intersect = findIntersection(head1, head2);

    if(intersect == NULL)
       cout<<"\nNo Intersection Found!";
    else
       cout<<"\nIntersect at: "<<intersect->data;

    return 0;
}

Output:

Linked List1: 4 1 5 3 4
Linked List2: 5 2 1 5 3 4 
Intersect at: 5

• Time Complexity: O(m*n) where m and n are the numbers of nodes in both lists.
• Space Complexity: O(1)

Approach 2: Two Pointer Approach. 

Follow the steps given below:

• Declare two pointers p1 and p2 and initialize them with head1 and head2.
• Traverse both the list using p1 and p2 one node at a time.
• When p1 reaches the end of the list then reassign it to head2.
• Similarly when p2 reaches the end of the list then reassign it to head1.
• Reassigning both the pointer will put them at an equal distance from the intersection point.
• In the second iteration, if both the pointer meet each other then return the intersection point else return NULL.

C++ Solution Code:

/*C++ Program to find Intersection of Two Linked List
using two pointer approach*/
#include<bits/stdc++.h>
using namespace std;

class ListNode{
    public:
      int data;
      ListNode *next;

    //constructor
    ListNode(int data){
        this->data = data;
        this->next = NULL;
    }  
};
//creating new node
ListNode *newNode(int data){
    ListNode *temp = new ListNode(data);
    temp->next = NULL;
    return temp;
}

//function to print linked list
void printList(ListNode *head){
    ListNode *temp = head;

    while(temp != NULL){
        cout<<temp->data<<" ";
        temp = temp->next;
    }
}
//Function to find intersection of two linked list
ListNode *findIntersection(ListNode *head1, ListNode *head2){

    ListNode* p1 = head1;
    ListNode* p2 = head2;

    while(p1 != NULL && p2 != NULL && p1 != p2){
        p1 = p1->next;
        p2 = p2->next;
            
        if(p1 == p2){
            return p1;
        }
        if(p1 == NULL) p1 = head2;
        if(p2 == NULL) p2 = head1;
    }
    return p1;
}
int main(){
    /*
    1st Linked List: 4->1->5->3->4
    2nd Linked List: 5->2->1->5->3->4
    Both are intersecting at 5
    */
    ListNode *head1 = new ListNode(4);
    head1->next = new ListNode(1);
    ListNode *commonNode;
    commonNode = new ListNode(5);
    commonNode->next = new ListNode(3);
    commonNode->next->next = new ListNode(4);
    head1->next->next = commonNode;

    ListNode *head2 = new ListNode(5);
    head2->next = new ListNode(2);
    head2->next->next = new ListNode(1);
    head2->next->next->next = commonNode;

    cout<<"Linked List1: ";
    printList(head1);

    cout<<"\nLinked List2: ";
    printList(head2);

    ListNode *intersect = findIntersection(head1, head2);

    if(intersect == NULL)
       cout<<"\nNo Intersection Found!";
    else
       cout<<"\nIntersect at: "<<intersect->data;

    return 0;
}

Output:

Linked List1: 4 1 5 3 4
Linked List2: 5 2 1 5 3 4 
Intersect at: 5

• Time Complexity: O(m+n) where m and n are the numbers of nodes in both lists.
• Space Complexity: O(1)

Next:

(getButton) #text=(Merge Two Sorted Linked List) #icon=(link) #color=(#2339bd)

Merge Two Sorted Linked List in C++.

Given heads of two sorted Linked lists list1 and list2 arrange in ascending order. Merge the two linked lists into one sorted linked list and return the head of the merged list.

Example 1: 
Input: 

list1: 1->2->3->4->NULL

list2: 1->3->5->NULL
Output: 1->1->2->3->3->4->5->NULL

Example 2:
Input: 

list1: 1->NULL
list2: 
Output: 1->NULL

Approach 1: Brute Force (Using Iteration). 

Follow the below steps to merge two sorted linked lists:

• If list1 is NULL then simply return the head of list2 and if list2 is NULL then simply return the head of list1.
• Declare a temp pointer that will point to a list containing the smaller value in the head node.
• One traverses the lists until one of them gets exhausted, chooses a smaller current node and links it with the tail of the merged list and then moves the current pointer of that list one step forward.
• If you reach a condition in which one of the lists got exhausted then simply link the remaining list to the tail of the merged list.

C++ Solution code:

/*C++ Program to Merge Sorted Linked List*/
#include<bits/stdc++.h>
using namespace std;

class ListNode{
    public:
      int data;
      ListNode *next;

    //constructor
    ListNode(int data){
        this->data = data;
        this->next = NULL;
    }  
};
//creating new node
ListNode *newNode(int data){
    ListNode *temp = new ListNode(data);
    temp->next = NULL;
    return temp;
}
//function to merge sorted linked lists
ListNode *mergeList(ListNode *list1, ListNode *list2){

    if(list1 == NULL ) return list2;
    if(list2 == NULL ) return list2;

    ListNode *ptr;
    if(list1->data > list2->data){
        ptr = list2;
        list2 = list2->next;
    }
    else{
        ptr = list1;
        list1 = list1->next;
    }

    ListNode *curr = ptr;

    while(list1 != NULL && list2 != NULL){

        if(list1->data < list2->data){
            curr->next = list1;
            list1 = list1->next;
        }
        else{
            curr->next = list2;
            list2 = list2->next;
        }
        curr = curr->next;
    }
    if(list1 != NULL){
        curr->next = list1;
    }
    else{
        curr->next = list2;
    }
    return ptr;
}
//function to print linked list
void printList(ListNode *head){
    ListNode *temp = head;

    while(temp != NULL){
        cout<<temp->data<<" ";
        temp = temp->next;
    }
}
int main(){
    //sorted list 1
    ListNode *list1 = newNode(1);
    list1->next = newNode(2);
    list1->next->next = newNode(3);
    list1->next->next->next = newNode(4);
    //sorted list 2
    ListNode *list2 = newNode(1);
    list2->next = newNode(3);
    list2->next->next = newNode(5);

    ListNode *merge = NULL;

    cout<<"Linked List1: ";
    printList(list1);

    cout<<"\nLinked List2: ";
    printList(list2);

    merge = mergeList(list1, list2);

    cout<<"\nSorted Linked List after merge: ";
    printList(merge);
    return 0;
}

Output:

Linked List1: 1 2 3 4
Linked List2: 1 3 5
Sorted Linked List after merge: 1 1 2 3 3 4 5

• Time Complexity: O(n) where n is the total number of nodes by adding list1 and list2.
• Space Complexity: O(1) no extra space is required.

Related Articles:

• Convert Binary Linked List to Integer.

• Find the Middle of the Singly Linked List in C++.

• Reverse a Singly Linked List in C++.

• Intersection Point of Two Linked Lists in C++.

• Detect Cycle in a Linked List in C++.

Reverse a Singly Linked List in C++.

Given the head of the singly linked list, reverse the given linked list and return it. 

Example 1: 
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Example 2:
Input: 1->0->4->7->2->3->NULL
Output: 3->2->7->4->0->1->NULL

Approach 1: Using Three Pointer.

In this approach, you need a three-pointer previous(prev), current(curr), and next(nxt) to keep track of nodes. 

Initialize three-pointers, prev as NULL, curr as head of the linked list and next as NULL.

Iterate through the linked list and follow below four steps to reverse the linked list:

• next = curr->next;
• curr->next = prev;
• prev = curr;
• curr = next;

C++ Solution code:

/*C++ Program to reverse a linked list*/
#include<bits/stdc++.h>
using namespace std;

class ListNode{
    public:
      int data;
      ListNode *next;

    //constructor
    ListNode(int data){
        this->data = data;
        this->next = NULL;
    }  
};
//creating new node
ListNode *newNode(int data){
    ListNode *temp = new ListNode(data);
    temp->next = NULL;
    return temp;
}
//function to reverse linked list
ListNode *reverseList(ListNode *head){

    ListNode *curr = head;
    ListNode *prev = NULL, *next = NULL;

    while(curr != NULL){
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    head = prev;
    return head;
}
//function to print linked list
void printList(ListNode *head){
    ListNode *temp = head;

    while(temp != NULL){
        cout<<temp->data<<" ";
        temp = temp->next;
    }
}
int main(){
    ListNode *head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);
    head->next->next->next = newNode(4);
    head->next->next->next->next = newNode(5);

    cout<<"Linked List before reverse: ";
    printList(head);

    ListNode *newHead = reverseList(head);

    cout<<"\nLinked List after reverse: ";
    printList(newHead);
    return 0;
}

Output:

Linked List before reverse: 1 2 3 4 5
Linked List after reverse: 5 4 3 2 1

• Time Complexity: O(n)
• Space Complexity: O(1)

Approach 2: Using Recursion.

This is a baisc recurison in which one base is when head is NULL or head->next is NULL. It means our list contain no node or it contain only one node and we cannot reverse a single node.

C++ Solution Code:

/*C++ Program to reverse a linked list using recursion*/
#include<bits/stdc++.h>
using namespace std;

class ListNode{
    public:
      int data;
      ListNode *next;

    //constructor
    ListNode(int data){
        this->data = data;
        this->next = NULL;
    }  
};
//creating new node
ListNode *newNode(int data){
    ListNode *temp = new ListNode(data);
    temp->next = NULL;
    return temp;
}
//function to reverse linked list
ListNode *reverseList(ListNode *head){

    //base case
    if(head == NULL || head->next == NULL)
       return head;

    ListNode *newHead = reverseList(head->next);
    head->next->next = head;

    head->next = NULL;

    return newHead;
}
//function to print linked list
void printList(ListNode *head){
    ListNode *temp = head;

    while(temp != NULL){
        cout<<temp->data<<" ";
        temp = temp->next;
    }
}
int main(){
    ListNode *head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);
    head->next->next->next = newNode(4);
    head->next->next->next->next = newNode(5);

    cout<<"Linked List before reverse: ";
    printList(head);

    ListNode *newHead = reverseList(head);

    cout<<"\nLinked List after reverse: ";
    printList(newHead);
    return 0;
}

Output:

Linked List before reverse: 1 2 3 4 5
Linked List after reverse: 5 4 3 2 1

• Time Complexity: O(n)
• Space Complexity: O(n) stack space

Related Articles:

• Convert Binary Linked List to Integer.

• Find the Middle of the Singly Linked List in C++.

• Merge Two Sorted Linked List in C++.

• Intersection Point of Two Linked Lists in C++.

• Detect Cycle in a Linked List in C++.

Find Middle of the Singly Linked List in C++.

Given a singly linked list and you need to return the middle node of the list and if the list has two middle nodes then return the second middle node.

Example 1: 
Input: 1->2->3->4->5
Output: 3

Example 2:
Input: 1->0->4->7->2->3
Output: 7

This problem is very simple to solve we just need to find the length of the linked list and then divide the length by 2 to get the indexing middle node. There are multiple ways to solve the problem let's discuss them one by one.

Approach 1: Brute Force Approach.

• Traverse the whole linked list to find the length of the linked list.
• Calculate the position of the middle node by diving the length of the linked list by 2. (len/2)
• After getting the position of the middle node traverse the linked list again using the temp pointer to find the address of the middle node.

C++ Solution Code:

/*C++ Program to find the middle element of the linked list*/
#include<bits/stdc++.h>
using namespace std;

class ListNode{
    public:
      int data;
      ListNode *next;

    //constructor
    ListNode(int data){
        this->data = data;
        this->next = NULL;
    }  
};
//creating new node
ListNode *newNode(int data){
    ListNode *temp = new ListNode(data);
    temp->next = NULL;
    return temp;
}
//Length of linked list
int getLength(ListNode *head){
    int len = 0;
    ListNode *temp = head;
    while(temp != NULL){
        temp = temp->next;
        len++;
    }
    return len;
}
//Function to get middle element
int getMiddle(ListNode* head){

    int len = getLength(head);

    ListNode *temp = head;
    int middle = len/2;

    while(middle--){
        temp = temp->next;
    }
    return temp->data;
}

int main(){
    ListNode *head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);
    head->next->next->next = newNode(4);
    head->next->next->next->next = newNode(5);

    cout<<"Middle Element: "<<getMiddle(head);

    return 0;
}

Output:

Middle Element: 3

• Time Complexity: O(n) + O(n/2) = O(n)
• Space Complexity: O(1)

Approach 2: Two-pointer approach (Slow Fast Pointer).

The second method is known as the Tortoise and Hare method or slow and fast pointer approach. In this approach, one pointer moves faster than the other pointer, and by the time the faster pointer reaches the end of the linked list, the slower point will reach the middle of the list. 

Step 1

Step 2

Step 3

• Initialize two pointers, slow and fast with the head of the linked list.
• Every time the slow moves one step the fast pointer move two-step at the same time.
• When the fast pointer reaches the end, you need to return the value present at the slow pointer which is pointing to the middle of the list.

C++ Solution code:

/*C++ Program to find the middle element of the linked list
using slow and fast pointer approach*/
#include<bits/stdc++.h>
using namespace std;

class ListNode{
    public:
      int data;
      ListNode *next;

    //constructor
    ListNode(int data){
        this->data = data;
        this->next = NULL;
    }  
};
//creating new node
ListNode *newNode(int data){
    ListNode *temp = new ListNode(data);
    temp->next = NULL;
    return temp;
}

//Function to get middle element
int getMiddle(ListNode* head){

    ListNode *slow = head;
    ListNode *fast = head;

    while(fast && fast->next){
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow->data;
}

int main(){
    ListNode *head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);
    head->next->next->next = newNode(4);
    head->next->next->next->next = newNode(5);

    cout<<"Middle Element: "<<getMiddle(head);

    return 0;
}

Output:

Middle Element: 3

• Time Complexity: O(n/2) = O(n)
• Space Complexity: O(1)

Related Articles:

• Convert Binary Linked List to Integer.

• Reverse a Singly Linked List in C++.

• Merge Two Sorted Linked List in C++.

• Intersection Point of Two Linked Lists in C++.

• Detect Cycle in a Linked List in C++.