Given a singly linked list, find middle of the linked list and set middle node of the linked list at beginning of the linked list.
Examples:
Input: 1 2 3 4 5 Output: 3 1 2 4 5 Input: 1 2 3 4 5 6 Output: 4 1 2 3 5 6
The idea is to first find middle of a linked list using two pointers, first one moves one at a time and second one moves two at a time. When second pointer reaches end, first reaches middle. We also keep track of previous of first pointer so that we can remove middle node from its current position and can make it head.
Javascript
<script> // Javascript program to make middle node // as head of Linked list // Link list node class Node { constructor(val) { this.data = val; this.next = null; } } var head; // Function to get the middle and set at // beginning of the linked list function setMiddleHead() { if (head == null) return; // To traverse list nodes one // by one one_node = head; // To traverse list nodes by // skipping one. two_node = head; // To keep track of previous of middle prev = null; while (two_node != null && two_node.next != null) { // for previous node of middle node prev = one_node; // Move one node each time two_node = two_node.next.next; // Move two node each time one_node = one_node.next; } // Set middle node at head prev.next = prev.next.next; one_node.next = head; head = one_node; } // To insert a node at the beginning of // linked list. function push(new_data) { // Allocate node new_node = new Node(new_data); // Link the old list of the new node new_node.next = head; // Move the head to point to the // new node head = new_node; } // A function to print a given linked list function printList(ptr) { while (ptr != null) { document.write(ptr.data + " "); ptr = ptr.next; } document.write("<br/>"); } // Driver function // Create a list of 5 nodes head = null; var i; for (i = 5; i > 0; i--) push(i); document.write(" list before: "); printList(head); setMiddleHead(); document.write(" list After: "); printList(head); // This code is contributed by aashish1995 </script> |
Output:
list before: 1 2 3 4 5 list After : 3 1 2 4 5
Time Complexity: O(n) when n is the total no of nodes in a linked list
Space Complexity: O(1) because using constant space
Please refer complete article on Make middle node head in a linked list for more details!
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!
