Example: Input: 1->2->3->4->5->NULL, m = 2, n = 4 Output: 1->4->3->2->5->NULL
Similar problem to reverse whole list.
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++:
#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; }
Output:
Input List is 1 -> 2 -> 3 -> 4 -> 5 Output List is 1 -> 4 -> 3 -> 2 -> 5