Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list.

Example:

Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

Reverse Linked List iterative and recursive in C++

To solve this problem we need to use 4 pointers. Below are the 4 pointers are used:

1. new_head- track head position (new_head.next = head) case: if head is reversed
2. pre – point to the start of the reversed list (0 to m-1)
3. cur- point to beginning of sub-list to be reversed
4. Move – point to the node will be reversed(overall traverse the list)

Once we set the first 3 pointers, we shall start reversing the list by making the immediate node after “cur” to be the immediate node after “pre”. Repeat it for n – m times.

Solution in C++:

/*
* File     : partition-list.cpp
*/

#include<iostream>
#include<vector>

using namespace std;

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

void insert_at_begenning ( struct Node **head_pointer, int data)
{
    // allocate memory for new node
    struct Node *temp_node = (struct Node*) malloc(sizeof(struct Node));

    // assign the data to new node
    temp_node->data = data;

    // initialize the new node to point to NULL
    temp_node->next = NULL;

    // if this is the first pointer, then this is the head pointer
    if (*head_pointer == NULL)
    {
        *head_pointer = temp_node;
    }
    else
    {
        // point the next of the present pointer to the head pointer
        temp_node->next = *head_pointer;

        //then move the reference of head pointer to the current pointer
        *head_pointer = temp_node;
    }
}

Node* reverseBetween(Node* head, int m, int n) 
{
    // create a dummy node to hold the head address, in case head needs to be reversed
    Node* new_head = new Node;

    //hold the address of the head.
    new_head -> next = head;

    // "pre" pointer to point to the starting of reversed list
    Node* pre = new_head;
    for (int i = 0; i < m - 1; i++)
        pre = pre -> next;

    // "cur" to point to the node next to "pre" node
    // Then move the immediate node after "cur" to be the 
    // immediate node after "pre".
    // Repeat it for n - m times
    Node* cur = pre -> next;
    for (int i = 0; i < n - m; i++) 
    {
        Node* move = cur -> next; 
        cur -> next = move -> next;
        move -> next = pre -> next;
        pre -> next = move;
    }

    // to avoid memory leak, assign the address of the head node to a temp pointer,
    // then delete the "new_head" node
    Node* temp = new_head -> next;
    delete new_head;
    return temp;
}

void display_list(struct Node **head_pointer)
{
    // take a reference to head pointer for navigation
    struct Node *temp = *head_pointer;

    while(temp != NULL)
    {
        if(temp->next != NULL)
            printf("%d -> ", temp->data);
        else
            printf("%d", temp->data);

        //navigate to next pointer
        temp = temp->next;
    }
    printf("\n");
}


int main()
{
    struct Node *list= NULL;
    struct Node *result= NULL;


    insert_at_begenning(&list,5);
    insert_at_begenning(&list,4);
    insert_at_begenning(&list,3);
    insert_at_begenning(&list,2);
    insert_at_begenning(&list,1);

    int m = 2;
    int n = 4;

    cout<<" Input List is\n";
    display_list(&list);

    result = reverseBetween(list, m, n);

    cout<<"\n Output List is\n";
    display_list(&result);

    cout<<endl;

return 0;

}

Input List is
1 -> 2 -> 3 -> 4 -> 5

Output List is
1 -> 4 -> 3 -> 2 -> 5