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++.

Convert Binary Linked List to Integer.

Given a Singly Linked List containing n nodes, each node of the list can hold either 0 or 1 and the most significant bit is present at the head of the linked list. The entire linked list is a binary representation of a decimal number. Return the decimal value represented by the given binary linked list. 

Note: The linked list is not empty and the maximum number of nodes will be less than 30.

Example 1: 
Input: 1->0->1->1
Output: 11

Example 2:
Input: 1->0->1
Output: 5

Approach 1: Converting Binary Using Arithmetic calculation.

You can solve this problem by diving the problem into two sub-problems:

• Find the number of binary digits present in the given linked list that is needed for the arithmetic calculation.
• Convert the Binary to a Decimal number using classic arithmetic calculation (see the above image).

C++ Solution Code:

//C++ Program to convert Binary Linked List to Decimal
#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 find length of linked list
int listLength(ListNode* head){
    ListNode *temp = head;
    int len = 0;
    while(temp != NULL){
        temp = temp->next;
        len++;
    }
    return len;
}
//function to convert binary to decimal
int getDecimalValue(ListNode *head){
    
    int len = listLength(head);
    int ans = 0;
    ListNode *temp = head;
    int i = 1;

    while(temp != NULL){
        int res = (temp->data)*pow(2, len-i);
        temp = temp->next;
        i++;
        ans += res;
    }
    return ans;
}
int main(){
    ListNode *head = newNode(1);
    head->next = newNode(0);
    head->next->next = newNode(1);

    cout<<"Integer Value: "<<getDecimalValue(head);

    return 0;
}

Output:

Integer Value: 5

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

Approach 2: Using Bit Manipulation.

In this approach, bit manipulation technique in which we will traverse the linked list starting from head till end. Updating the current value with head->next->value. Updating the result by shifting the digit by one to the left and performing logical OR with current vlaue.

C++ Solution code:

/*C++ Program to convert Binary Linked List to Decimal
Using bit manipulation*/
#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 convert binary to decimal
int getDecimalValue(ListNode *head){
    
    int num = head->data;
    while (head->next != NULL)
    {
        num = (num << 1) | head->next->data;
        head = head->next;
    }
    
    return num;
}
int main(){
    ListNode *head = newNode(1);
    head->next = newNode(0);
    head->next->next = newNode(1);

    cout<<"Integer Value: "<<getDecimalValue(head);

    return 0;
}

Output:

Integer Value: 5

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

Related Articles:

• 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++.

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

Program to Find Sum of All Odd Length Subarrays.

Given a positive integer array num of size n, calculate and return the sum of all possible odd-length subarrays of num.

Example:

Example 1:
Input: num[] = {1, 3, 2, 5, 6};
Output: 63

Explanation: 
List of Odd length subarrays:

[1] = 1

[3] = 3

[2] = 2

[5] = 5

[6] = 6

[1, 3, 2] = 6

[3, 2, 5] = 10

[2, 5, 6] = 13

[1, 3, 2, 5, 6] = 17

Sum of all odd length arrays: 1+3+2+5+6+6+10+13+17 = 63

Example 2:
Input: num[] = {3, 5}
Output: 8

Explanation:

List of Odd length subarrays:

[3] = 3

[5] = 5

Sum of all odd length arrays: 3+5 = 8

Approach 1: Brute Force Solution.

You can quickly get all possible subarrays by running two nested loops but the critical point of this problem is that you need to find only all odd-length subarrays. 

You can use a generalized formula that if [(last_position_of_subarray - first_positon_ of _subarray)%2 == 0] then the length is odd else the length is even. You can then add the elements of that subarray to your answer.

C++ Solution Code:

/*C++ code to find sum of odd length subarray*/
#include<bits/stdc++.h>
using namespace std;

int sumOfOddSubarray(vector<int> &num){
    int total = 0;

    for(int i = 0; i < num.size(); i++){
        int sum = 0;
        for(int j = i; j < num.size(); j++){
            sum += num[j];
            if((j - i)%2 == 0)
              total += sum;
        }
    }
    return total;
}

int main(){
    vector<int> num = {1, 3, 2, 5, 6};

    int ans = sumOfOddSubarray(num);
    cout<<"Sum Of Odd Length subarrays: "<<ans;

    return 0;   
}

Output:

Sum Of Odd Length subarrays: 63

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

Approach 2: Using Math.

In the previous approach, you check for all possible subarrays but in this approach, you are going to derive a mathematical formula to solve this problem in O(n) time complexity. This solution might be a little confusing but if you don't give up I am sure you will understand it well. Let's start,

If you observe the question carefully you will find that we only need the sum of subarrays we don't need to print them anywhere so if somehow you count the number of occurrences of each element in all possible odd-length subarray then you can multiply each element with their number of occurrences and sum them up together then you can get your required answer. Let's understand with one example.

In this above example image, we have taken only all odd-length subarrays 

Given: [1, 4, 2, 5, 3]

Element      Number of occurance      Sum

ar[0] = 1        3                    1x3 = 3

ar[1] = 4        4                    4x4 = 16

ar[2] = 2        5                    2x5 = 10

ar[3] = 5        4                    5x4 = 20

ar[4] = 3        3                    3x3 = 9

                                    Total = 58

Explanation: 

arr[2] = 2 present in 5 times(one time in row first, 

three times in row second and one time in row third)

similarly we need to count for all elements.

To create a subarray that contains arr[i]  we can take 0, 1, 2, ..... i element on the left hand side from arr[0] to  arr[i] and you get (i+1) choices to include arr[i] in the subarray. Similarly, you can take 0, 1, 2, ...... n-1-i element on the right-hand side from arr[i] to arr[n-1]. and you will get (n-i) choices to include arr[i] in the subarray.

In total you will get [k = (i+1)*(n-i)] number of subarrays that contains arr[i] so,

There is (k+1)/2 subarray with the odd length that contains arr[i].

There is (k/2) subarray with even length that contains arr[i].

We can derive a general formula with all the above observations and calculations for finding the number of times an element is occurring for odd-length subarrays.

n = ((i+1)*(n-i)+1)/2

C++ Solution Code:

/*C++ code to find sum of odd length subarray (Optimized)*/
#include<bits/stdc++.h>
using namespace std;

int sumOfOddSubarray(vector<int> &num){
    int total = 0;
    int n = num.size();

    for(int i = 0; i < n; i++){
        total += ((i+1)*(n-i)+1)/2 * num[i];
    }
    return total;
}

int main(){
    vector<int> num = {1, 4, 2, 5, 3};

    int ans = sumOfOddSubarray(num);
    cout<<"Sum Of Odd Length subarrays: "<<ans;

    return 0;   
}

Output:

Sum Of Odd Length subarrays: 58

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

Program to Count Number of Good Pair.

Given an integer array num of size n, return the count of possible good pairs. A pair of elements is called a good pair if (num[i] == num[j]) and i < j.

Example:

Example 1:
Input: num[] = {2, 1, 3, 2, 2, 3};
Output: 4

Explanation: 
There are four good pairs (0, 3), (0, 4), (2, 5) and (3, 4)

Example 2:
Input: num[] = {3, 3, 3, 3}
Output: 6

Approach 1: Brute Force Solution.

Take a count variable and initialize it with 0. Run two nested for loops for each element of the array, pick each element one by one and then compare it with the remaining element and then keep on increasing the count variable whenever the given condition is satisfied. 

C++ Solution Code:

/*C++ code for count number of good pairs*/
#include<bits/stdc++.h>
using namespace std;

int goodPairs(vector<int> &num){
    int count = 0;

    for(int i = 0; i < num.size(); i++){
        for(int j = i+1; j < num.size(); j++){
            if(num[i] == num[j])
              count++;
        }
    }
    return count;
}

int main(){
    vector<int> num = {2, 1, 3, 2, 2, 3};

    int count = goodPairs(num);
    cout<<"Number of Good Pairs: "<<count;

    return 0;   
}

Output:

Number of Good Pairs: 4

• Time Complexity: Running two nested loops for n elements takes O(n^2) time complexity.
• Space Complexity: No extra space is required in the above solution so space complexity is O(1).

Approach 2: Using Hash Map.

You can optimize the previous solution by using a hash map to get the count of each unique element of the array. 

Given num = [2, 1, 3, 2, 2, 3]

Structure of map:

Key      Value(count)

 2          3 (Value 2 appears 3 times)

 1          1 (Value 1 appears 1 times)

 3          2 (Value 3 appears 2 times)       

When you have n number of similar values then it can create [n*(n-1)/2] number of unique good pairs. 

[3, 3, 3, 3]

Number of Good Pairs = 4*(4-1)/2 = 6

Similarly, you can calculate the number of unique good pairs for each value of the map and sum them up to get the total number of good pairs possible from all array elements.

Key      Value(count)      Good Pairs

 2          3            [3*(3-1)/2 = 3] 

 1          1            [1*(1-1)/2 = 0]

 3          2            [2*(2-1)/2 = 1]  

Total number of Good Pairs = 3+0+1 = 4     

C++ Solution Code:

/*C++ code for count number of good pairs(Optimized)*/
#include<bits/stdc++.h>
using namespace std;

int goodPairs(vector<int> &num){
    int count = 0;
    unordered_map<int, int> mp;

    //Storing count of each unique element
    for(int i = 0; i < num.size(); i++){
        mp[num[i]]++;
    }

    //counting good pairs
    for(auto i:mp){
        int n = i.second;
        count += (n*(n-1))/2;
    }
    return count;
}

int main(){
    vector<int> num = {2, 1, 3, 2, 2, 3};

    int count = goodPairs(num);
    cout<<"Number of Good Pairs: "<<count;

    return 0;   
}

Output:

Number of Good Pairs: 4

• Time Complexity: We run two separate loops one for storing the count in the map and the next loop for counting good pairs so the average time complexity will be O(n).
• Space Complexity: We are using one map to store the count of elements so space complexity will be O(n).

Next:

(getButton) #text=(Count Number of Elements Smaller than Current Element) #icon=(link) #color=(#2339bd)