Given a linked list, the task is to rearrange the linked list in the following manner:
- Reverse the second half of given linked list.
-
- First element of the linked list is the first element of first half.
- Second element of the linked list is the first element of second half.
Examples:
Input: 1->2->3->4->5 Output: 1->5->2->4->3 Input: 1->2->3->4->5->6 Output: 1->6->2->5->3->4
Approach:
Initially find the mid node of the linked list. The approach has been discussed here. Reverse the linked list from mid to end. Once the linked list is reversed, traverse from the start and insert a node from the first half of the list and another node from the back half of the linked list simultaneously. Continue this process until the middle node is reached.
Once the middle node is reached, point the node just before the middle node to NULL.
Below is the implementation of the above approach:
C++
// C++ program to sandwich the last part of// linked list in between the first part of// the linked list#include<bits/stdc++.h>#include <stdio.h>using namespace std;struct node { int data; struct node* next;}; // Function to reverse Linked Liststruct node* reverseLL(struct node* root){ struct node *prev = NULL, *current = root, *next; while (current) { next = current->next; current->next = prev; prev = current; current = next; } // root needs to be updated after reversing root = prev; return root;} // Function to modify Linked Listvoid modifyLL(struct node* root){ // Find the mid node struct node *slow_ptr = root, *fast_ptr = root; while (fast_ptr && fast_ptr->next) { fast_ptr = fast_ptr->next->next; slow_ptr = slow_ptr->next; } // Reverse the second half of the list struct node* root2 = reverseLL(slow_ptr->next); // partition the list slow_ptr->next = NULL; struct node *current1 = root, *current2 = root2; // insert the elements in between while (current1 && current2) { // next node to be traversed in the first list struct node* dnext1 = current1->next; // next node to be traversed in the first list struct node* dnext2 = current2->next; current1->next = current2; current2->next = dnext1; current1 = dnext1; current2 = dnext2; }} // Function to insert node after the endvoid insertNode(struct node** start, int val){ // allocate memory struct node* temp = (struct node*)malloc(sizeof(struct node)); temp->data = val; // if first node if (*start == NULL) *start = temp; else { // move to the end pointer of node struct node* dstart = *start; while (dstart->next != NULL) dstart = dstart->next; dstart->next = temp; }} // function to print the linked listvoid display(struct node** start){ struct node* temp = *start; // traverse till the entire linked // list is printed while (temp->next != NULL) { printf("%d->", temp->data); temp = temp->next; } printf("%d\n", temp->data);} // Driver Codeint main(){ // Odd Length Linked List struct node* start = NULL; insertNode(&start, 1); insertNode(&start, 2); insertNode(&start, 3); insertNode(&start, 4); insertNode(&start, 5); printf("Before Modifying: "); display(&start); modifyLL(start); printf("After Modifying: "); display(&start); // Even Length Linked List start = NULL; insertNode(&start, 1); insertNode(&start, 2); insertNode(&start, 3); insertNode(&start, 4); insertNode(&start, 5); insertNode(&start, 6); printf("\nBefore Modifying: "); display(&start); modifyLL(start); printf("After Modifying: "); display(&start); return 0;} |
Java
// Java program to sandwich the // last part of linked list in // between the first part of// the linked listimport java.util.*;class node { int data; node next; node(int key) { data = key; next = null; }}class GFG{ // Function to reverse// Linked Listpublic static node reverseLL(node root){ node prev = null, current = root, next; while (current!= null) { next = current.next; current.next = prev; prev = current; current = next; } // root needs to be // updated after reversing root = prev; return root;}// Function to modify// Linked Listpublic static void modifyLL( node root){ // Find the mid node node slow_ptr = root, fast_ptr = root; while (fast_ptr != null && fast_ptr.next != null) { fast_ptr = fast_ptr.next.next; slow_ptr = slow_ptr.next; } // Reverse the second // half of the list node root2 = reverseLL(slow_ptr.next); // partition the list slow_ptr.next = null; node current1 = root, current2 = root2; // insert the elements in between while (current1 != null && current2 != null) { // next node to be traversed // in the first list node dnext1 = current1.next; // next node to be traversed // in the first list node dnext2 = current2.next; current1.next = current2; current2.next = dnext1; current1 = dnext1; current2 = dnext2; }}// Function to insert // node after the endpublic static node insertNode(node start, int val){ // allocate memory node temp = new node(val); // if first node if (start == null) start = temp; else { // move to the end // pointer of node node dstart = start; while (dstart.next != null) dstart = dstart.next; dstart.next = temp; } return start;}// function to print// the linked listpublic static void display(node start){ node temp = start; // traverse till the // entire linked // list is printed while (temp.next != null) { System.out.print(temp.data + "->"); temp = temp.next; } System.out.println(temp.data);}// Driver Codepublic static void main(String args[]){ // Odd Length Linked List node start = null; start = insertNode(start, 1); start = insertNode(start, 2); start = insertNode(start, 3); start = insertNode(start, 4); start = insertNode(start, 5); System.out.print("Before Modifying: "); display(start); modifyLL(start); System.out.print("After Modifying: "); display(start); // Even Length Linked List start = null; start = insertNode(start, 1); start = insertNode(start, 2); start = insertNode(start, 3); start = insertNode(start, 4); start = insertNode(start, 5); start = insertNode(start, 6); System.out.print("Before Modifying: "); display(start); modifyLL(start); System.out.print("After Modifying: "); display(start);}} |
Python3
# Python3 program to sandwich the last part of# linked list in between the first part of# the linked list class node: def __init__(self): self.data = 0 self.next = None # Function to reverse Linked Listdef reverseLL(root): prev = None current = root while (current): next = current.next; current.next = prev; prev = current; current = next; # root needs to be updated after reversing root = prev; return root; # Function to modify Linked Listdef modifyLL(root): # Find the mid node slow_ptr = root fast_ptr = root; while (fast_ptr and fast_ptr.next): fast_ptr = fast_ptr.next.next; slow_ptr = slow_ptr.next; # Reverse the second half of the list root2 = reverseLL(slow_ptr.next); # partition the list slow_ptr.next = None; current1 = root current2 = root2; # insert the elements in between while (current1 and current2): # next node to be traversed in the first list dnext1 = current1.next; # next node to be traversed in the first list dnext2 = current2.next; current1.next = current2; current2.next = dnext1; current1 = dnext1; current2 = dnext2; # Function to insert node after the enddef insertNode(start, val): # allocate memory temp = node() temp.data = val; # if first node if (start == None): start = temp; else: # move to the end pointer of node dstart = start; while (dstart.next != None): dstart = dstart.next; dstart.next = temp; return start # function to print the linked listdef display(start): temp = start; # traverse till the entire linked # list is printed while (temp.next != None): print("{}->".format(temp.data), end = '') temp = temp.next; print("{}".format(temp.data))# Driver Codeif __name__=='__main__': # Odd Length Linked List start = None; start = insertNode(start, 1); start = insertNode(start, 2); start = insertNode(start, 3); start = insertNode(start, 4); start = insertNode(start, 5); print("Before Modifying: ", end = ''); display(start); modifyLL(start); print("After Modifying: ", end = ''); display(start); # Even Length Linked List start = None; start = insertNode(start, 1); start = insertNode(start, 2); start = insertNode(start, 3); start = insertNode(start, 4); start = insertNode(start, 5); start = insertNode(start, 6); print("\nBefore Modifying: ", end = ''); display(start); modifyLL(start); print("After Modifying: ", end = '') display(start);# This code is contributed by rutvik_56 |
C#
// C# program to sandwich the last part // of linked list in between the first // part of the linked listusing System;public class node { public int data; public node next; public node(int key) { data = key; next = null; } } public class GFG { // Function to reverse // Linked List public static node reverseLL(node root) { node prev = null, current = root, next; while (current!= null) { next = current.next; current.next = prev; prev = current; current = next; } // root needs to be // updated after reversing root = prev; return root; } // Function to modify // Linked List public static void modifyLL( node root) { // Find the mid node node slow_ptr = root, fast_ptr = root; while (fast_ptr != null && fast_ptr.next != null) { fast_ptr = fast_ptr.next.next; slow_ptr = slow_ptr.next; } // Reverse the second // half of the list node root2 = reverseLL(slow_ptr.next); // partition the list slow_ptr.next = null; node current1 = root, current2 = root2; // insert the elements in between while (current1 != null && current2 != null) { // next node to be traversed // in the first list node dnext1 = current1.next; // next node to be traversed // in the first list node dnext2 = current2.next; current1.next = current2; current2.next = dnext1; current1 = dnext1; current2 = dnext2; } } // Function to insert // node after the end public static node insertNode(node start, int val) { // allocate memory node temp = new node(val); // if first node if (start == null) start = temp; else { // move to the end // pointer of node node dstart = start; while (dstart.next != null) dstart = dstart.next; dstart.next = temp; } return start; } // function to print // the linked list public static void display(node start) { node temp = start; // traverse till the // entire linked // list is printed while (temp.next != null) { Console.Write(temp.data + "->"); temp = temp.next; } Console.WriteLine(temp.data); } // Driver Code public static void Main(String []args) { // Odd Length Linked List node start = null; start = insertNode(start, 1); start = insertNode(start, 2); start = insertNode(start, 3); start = insertNode(start, 4); start = insertNode(start, 5); Console.Write("Before Modifying: "); display(start); modifyLL(start); Console.Write("After Modifying: "); display(start); // Even Length Linked List start = null; start = insertNode(start, 1); start = insertNode(start, 2); start = insertNode(start, 3); start = insertNode(start, 4); start = insertNode(start, 5); start = insertNode(start, 6); Console.Write("Before Modifying: "); display(start); modifyLL(start); Console.Write("After Modifying: "); display(start); } } // This code has been contributed // by 29AjayKumar |
Javascript
<script> // JavaScript program to sandwich the last part // of linked list in between the first // part of the linked list class node { constructor(key) { this.data = key; this.next = null; } } // Function to reverse // Linked List function reverseLL(root) { var prev = null, current = root, next; while (current != null) { next = current.next; current.next = prev; prev = current; current = next; } // root needs to be // updated after reversing root = prev; return root; } // Function to modify // Linked List function modifyLL(root) { // Find the mid node var slow_ptr = root, fast_ptr = root; while (fast_ptr != null && fast_ptr.next != null) { fast_ptr = fast_ptr.next.next; slow_ptr = slow_ptr.next; } // Reverse the second // half of the list var root2 = reverseLL(slow_ptr.next); // partition the list slow_ptr.next = null; var current1 = root, current2 = root2; // insert the elements in between while (current1 != null && current2 != null) { // next node to be traversed // in the first list var dnext1 = current1.next; // next node to be traversed // in the first list var dnext2 = current2.next; current1.next = current2; current2.next = dnext1; current1 = dnext1; current2 = dnext2; } } // Function to insert // node after the end function insertNode(start, val) { // allocate memory var temp = new node(val); // if first node if (start == null) start = temp; else { // move to the end // pointer of node var dstart = start; while (dstart.next != null) dstart = dstart.next; dstart.next = temp; } return start; } // function to print // the linked list function display(start) { var temp = start; // traverse till the // entire linked // list is printed while (temp.next != null) { document.write(temp.data + "->"); temp = temp.next; } document.write(temp.data + "<br>"); } // Driver Code // Odd Length Linked List var start = null; start = insertNode(start, 1); start = insertNode(start, 2); start = insertNode(start, 3); start = insertNode(start, 4); start = insertNode(start, 5); document.write("Before Modifying: "); display(start); modifyLL(start); document.write("After Modifying: "); display(start); // Even Length Linked List start = null; start = insertNode(start, 1); start = insertNode(start, 2); start = insertNode(start, 3); start = insertNode(start, 4); start = insertNode(start, 5); start = insertNode(start, 6); document.write("<br>Before Modifying: "); display(start); modifyLL(start); document.write("After Modifying: "); display(start); // This code is contributed by rdtank. </script> |
Output
Before Modifying: 1->2->3->4->5 After Modifying: 1->5->2->4->3 Before Modifying: 1->2->3->4->5->6 After Modifying: 1->6->2->5->3->4
Time Complexity: O(N)
Exercise: Solve the question without reversing the Linked List from the middle node.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
