In this post, we have demonstrated ways in which we can not only reverse a singly linked list but also some part of Singly Linked List. It takes linear time O(N) to Reverse part of Singly Linked List.

Table of contents:

1. Introduction to reversing Linked List
2. Approach 1 to Reverse part of Singly Linked List
3. Approach 2 to Reverse part of Singly Linked List

This is similar to Leetcode problem 92. Reverse Linked List II. Let us get started with Reverse part of Singly Linked List.

Introduction to reversing Linked List

To reverse part of a linked list we first need to break down the problem, into a smaller manageable sub-problems after which we will use knowledge gained from solving the sub-problem and apply it to solving the larger problem.

We need to understand how to go about reversing a linked list then coming to the main problem, all we need to do is to apply that knowledge to some part of the whole linked list.

To reverse a linked list all we need to do is change the pointers linking the nodes to point backwards and make the head pointer point to the last node and next pointer of previous head point to null making it the end of the list.

Example

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> NULL

7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> NULL

Algorithm:

1. We first initialize 3 pointers, prevNode, currNode, nextNode.
2. We go through the linked list performing the following operations;
   -> Store the next of currNode.
   -> Make the next of currNode to prevNode.
   -> Move prevNode and currNode one step forward.
3. Loop stops when currNode becomes null, at this point prevNode is at the last node in list, we assign it to head pointer making it begining of the list.

Pseudocode:

while currNode != null
    next = currNode.next
    currNode.next = prevNode
    prevNode = currNode
    currNode = next
head = prevNode

And gif to illustrate the process of linked list reversal for a clearer picture.

Now having that idea in mind we can apply it to our previous problem of reversing part of a linked list. But first we need to understand it programmatically, what are the inputs and outputs, with these we can develop an algorithm to solve the problem.

The function will take a head of a linked list and two pointers m and n, one pointing to the start position of a part of the linked list and the other pointing to the end position of part of the linked list respectively.
Output will be the head of the reversed linked list.

Input: *head, m, n
Output: *head of reversed linked list

Approach 1 to Reverse part of Singly Linked List

In this approach we will use the reverse procedure on the part we need to reverse in the linked list.

Before we proceed to other parts of the program it is always wise to evaluate the inputs to avoid errors and unecessary computations. In this case we can check if m and n are equal, if so this means there is nothing to reverse. We can also check if m is greater than n, this will be invalid, the start should be less than the end, here we return head.

This approach relies heavily on the pointers we assign and where we position them in the list.

We will initialize 4 pointers.

• revStart -> placed at the start of part that will be reversed.
• revEnd -> placed at the end of part that will be reversed.
• revPrev -> placed at the previous position that is before revStart.
• revNext -> placed at the next position after revEnd.

We first iterate through the list placing all these pointers in their respective positions.
After this procedure, revStart is at the start of the part that needs reversal, so we pass it as head to reverse procedure which reverses the selected part.
Finally we rejoin the list with the reversed selected part by reasigning the pointers.

Code:

#include<bits/stdc++.h>

struct ListNode{
    int data;
    ListNode *next;
};

ListNode* reverse(ListNode *head){
    ListNode* prevNode = NULL;
    ListNode* currNode = head;
    while(currNode){
        ListNode* next = currNode->next;
        currNode->next = prevNode;
        prevNode = currNode;
        currNode = next;
    }
    return prevNode;
}

ListNode* reversePart(ListNode* head, int m, int n){
// single element in selected part
    if(m == n)
        return head;
        
// Initialize pointers
    ListNode* revStart = NULL;
    ListNode* revEnd = NULL;
    ListNode* revPrev = NULL;
    ListNode* revNext = NULL;
    ListNode* currNode = head;
    int i = 1;
    
// place all pointers in their respective positions
    while(currNode && i <= n){
        if( i < m)
            revPrev = currNode;
        if(i == m)
            revStart = currNode;
        if(i == n){
            revEnd = currNode;
            revNext = currNode->next;
        }
        currNode = currNode->next;
        i++;
    }
    revEnd->next = NULL;
    
// reverse selected part
    revEnd = reverse(revStart);

//Rejoin the reversed part back to original list
    if(revPrev)
        revPrev->next = revEnd;
    else
        head = revEnd;

    revStart->next = revNext;
    return head;
}

Time and Space Complexity

This procedure runs in linear time O(n), where n is the number of nodes in the list.
The space complexity is constant O(1), no extra space used.

Approach 2 to Reverse part of Singly Linked List

We can also approach the problem in simpler manner, the overall idea is the same but the details will differ a bit.
We initialize two variables prevNode and currNode.
We start by skipping the first m nodes using a loop and assign a variable currNode at this position, start of selected part for reversal.
prevNode will be at (m-1)th position.

We initialize revStart to start at the selected part for reversal and revEnd as NULL.
We then iterate the selected part using a loop while reversing the nodes from revStart to revEnd.
At this point the selected part is reversed.
We rejoin the list with the reversed selected part by reasigning the pointers which concludes our algorithm.

Code.

ListNode* reversePart(ListNode* head, int m, int n){
//start cannot be smaller than end position
    if(m > n)
        return head;

    ListNode* prevNode = NULL;
    ListNode* currNode = NULL;

// skip the first m nodes
    for(int i = 1; currNode != NULL && i < m; i++){
        prevNode = currNode;
        currNode = currNode->next;
    }

// assign pointers to start and end of selected part
    ListNode* revStart = currNode;
    ListNode* revEnd = NULL;

// reverse the selected part
    for(int i = 1; currNode != NULL && i <= n-m+1; i++){
        ListNode* next = currNode->next;
        currNode->next = revEnd;
        revEnd = currNode;
    }
    
// reassign pointers and rejoin to main list
    if(revStart != NULL){
        revStart->next = currNode;
        if(prevNode != NULL)
            prevNode->next = revEnd;
        else
            head = revEnd;
    }
    return head;
}

Time and Space Complexity

The time complexity is linear O(n), n being the number of nodes in the list.
The space complexity is constant O(1), no extra space required.

Note: The code used here only solves the described problem, the full code can be found in the link below.

Questions

Can you think of situations where we would need to reverse part of a linked list to solve a problem whose solution is implemented using a linked list?

Full Code

With this article at OpenGenus, you must have the complete idea of Reversing part of Singly Linked List.