Move the Kth element to the Front of a Doubly Linked List
Given a doubly linked list and an integer K, you need to move the Kth element to the front of the list while maintaining the order of the other elements.
Examples:
Input: DLL: 2 <-> 6 <-> 3 <-> 8 <-> 11 <-> 23 <-> 7 -> NULL, K = 4
Output: 8 <-> 2 <-> 6 <-> 3 <-> 11 <-> 23 <-> 7 -> NULL
Explanation: We move the 4th element (with value 8) to the front of the list while maintaining the order of the other elements.Input: DLL: 5 <-> 2 <-> 8 <-> 4 <-> 5 <-> 6 -> NULL, K = 2
Output: 2 <-> 5 <-> 8 <-> 4 <-> 5 <-> 6 -> NULL
Explanation: In this case, moving the 2nd element (with value 2) to the front of the list while maintaining the order of the other elements.
Approach: To solve the problem follow the below idea:
The approach to moving the Kth element to the front of the doubly linked list involves traversing the list to locate the Kth element and then rearranging the pointers to position it at the front.
- We start by checking for invalid input and special handling if K is 1.
- Then, we traverse the list to find the Kth element while tracking its previous node. We update the pointers of the previous and next nodes to bypass the Kth element, effectively removing it from its current position.
- Finally, we make the Kth element the new head by updating its pointers and the head pointer itself. This approach efficiently relocates the Kth element to the front while maintaining the order of the remaining elements, optimizing access to that specific element.
Steps of the approach:
- Check for invalid input: Ensure the doubly linked list is not empty, K is a positive integer, and K is not 1 (for the special case).
- For K > 1, traverse the list to locate the Kth element while tracking its previous node.
- Check if K is greater than the list’s length; if so, exit without making changes.
- If K is valid, adjust pointers to bypass the Kth node and remove it from its current position.
- Make the Kth element the new head of the list by updating pointers.
- Ensure bidirectional linkage between the Kth element and the former head.
- Update the head pointer to point to the Kth element.
Below is the C++ implementation for above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Definition for a doubly-linked list node. struct Node { int data; Node* next; Node* prev; }; // Function to move the Kth element to the // front of the doubly linked list. void moveKthToFront(Node*& head, int K) { // Invalid input or K is 1 if (head == nullptr || K < 1 || K == 1) { return ; } Node* current = head; Node* prevKth = nullptr; for ( int i = 1; i < K && current; i++) { prevKth = current; current = current->next; } // K is greater than the length of the list if (current == nullptr) { return ; } // Adjust pointers to bypass the Kth node if (prevKth) { prevKth->next = current->next; } if (current->next) { current->next->prev = prevKth; } // Make the Kth node the new head current->next = head; head->prev = current; current->prev = nullptr; head = current; } // Function to print the doubly // linked list. void printList(Node* head) { while (head) { cout << head->data; if (head->next) { cout << " <-> "; } head = head->next; } cout << " -> NULL" << std::endl; } // Drivers code int main() { // Create the first example doubly linked list: 2 <-> 6 // <-> 3 <-> 8 <-> 11 <-> 23 <-> 7 // Create the nodes Node* node1 = new Node{ 2, nullptr, nullptr }; Node* node2 = new Node{ 6, nullptr, node1 }; Node* node3 = new Node{ 3, nullptr, node2 }; Node* node4 = new Node{ 8, nullptr, node3 }; Node* node5 = new Node{ 11, nullptr, node4 }; Node* node6 = new Node{ 23, nullptr, node5 }; Node* node7 = new Node{ 7, nullptr, node6 }; // Connect the nodes node1->next = node2; node2->next = node3; node3->next = node4; node4->next = node5; node5->next = node6; node6->next = node7; // Set the head of the list Node* head = node1; // Print the original list cout << "Original List: "; printList(head); // Move the 4th element to the front moveKthToFront(head, 4); // Print the modified list cout << "Modified List: "; printList(head); return 0; } |
Java
// Java code for the above approach: class Node { int data; Node next; Node prev; public Node( int data, Node next, Node prev) { this .data = data; this .next = next; this .prev = prev; } } public class Main { // Function to move the Kth element to the front of the doubly linked list. static void moveKthToFront(Node head, int K) { // Invalid input or K is 1 if (head == null || K < 1 || K == 1 ) { return ; } Node current = head; Node prevKth = null ; for ( int i = 1 ; i < K && current != null ; i++) { prevKth = current; current = current.next; } // K is greater than the length of the list if (current == null ) { return ; } // Adjust pointers to bypass the Kth node if (prevKth != null ) { prevKth.next = current.next; } if (current.next != null ) { current.next.prev = prevKth; } // Make the Kth node the new head current.next = head; head.prev = current; current.prev = null ; head = current; } // Function to print the doubly linked list. static void printList(Node head) { while (head != null ) { System.out.print(head.data); if (head.next != null ) { System.out.print( " <-> " ); } head = head.next; } System.out.println( " -> NULL" ); } // Driver code public static void main(String[] args) { // Create the first example doubly linked // list: 2 <-> 6 <-> 3 <-> 8 <-> 11 <-> 23 <-> 7 // Create the nodes Node node1 = new Node( 2 , null , null ); Node node2 = new Node( 6 , null , node1); Node node3 = new Node( 3 , null , node2); Node node4 = new Node( 8 , null , node3); Node node5 = new Node( 11 , null , node4); Node node6 = new Node( 23 , null , node5); Node node7 = new Node( 7 , null , node6); // Connect the nodes node1.next = node2; node2.next = node3; node3.next = node4; node4.next = node5; node5.next = node6; node6.next = node7; // Set the head of the list Node head = node1; // Print the original list System.out.print( "Original List: " ); printList(head); // Move the 4th element to the front moveKthToFront(head, 4 ); // Print the modified list System.out.print( "Modified List: " ); printList(head); } } // this code is contributed by uttamdp_10 |
Python3
# Python code for the above approach class Node: def __init__( self , data, next = None , prev = None ): self .data = data self . next = next self .prev = prev # Function to move the Kth element to the front of the doubly linked list. def move_kth_to_front(head, K): # Invalid input or K is 1 if not head or K < 1 or K = = 1 : return current = head prev_kth = None for i in range ( 1 , K): if current: prev_kth = current current = current. next # K is greater than the length of the list if not current: return # Adjust pointers to bypass the Kth node if prev_kth: prev_kth. next = current. next if current. next : current. next .prev = prev_kth # Make the Kth node the new head current. next = head head.prev = current current.prev = None head = current # Function to print the doubly linked list. def print_list(head): while head: print (head.data, end = "") if head. next : print ( " <-> " , end = "") head = head. next print ( " -> NULL" ) # Driver code if __name__ = = "__main__" : # Create the first example doubly linked list: 2 <-> 6 <-> 3 <-> 8 <-> 11 <-> 23 <-> 7 # Create the nodes node1 = Node( 2 ) node2 = Node( 6 ) node3 = Node( 3 ) node4 = Node( 8 ) node5 = Node( 11 ) node6 = Node( 23 ) node7 = Node( 7 ) # Connect the nodes node1. next = node2 node2. next = node3 node3. next = node4 node4. next = node5 node5. next = node6 node6. next = node7 # Set the head of the list head = node1 # Print the original list print ( "Original List: " , end = "") print_list(head) # Move the 4th element to the front move_kth_to_front(head, 4 ) # Print the modified list print ( "Modified List: " , end = "") print_list(head) # This code is contributed by guptapratik |
C#
using System; // Definition for a doubly-linked list node. public class Node { public int Data; public Node Next; public Node Prev; public Node( int data, Node next, Node prev) { Data = data; Next = next; Prev = prev; } } class Program { // Function to move the Kth element to the front of the doubly linked list. public static void MoveKthToFront( ref Node head, int K) { // Invalid input or K is 1 if (head == null || K < 1 || K == 1) { return ; } Node current = head; Node prevKth = null ; for ( int i = 1; i < K && current != null ; i++) { prevKth = current; current = current.Next; } // K is greater than the length of the list if (current == null ) { return ; } // Adjust pointers to bypass the Kth node if (prevKth != null ) { prevKth.Next = current.Next; } if (current.Next != null ) { current.Next.Prev = prevKth; } // Make the Kth node the new head current.Next = head; head.Prev = current; current.Prev = null ; head = current; } // Function to print the doubly linked list. public static void PrintList(Node head) { while (head != null ) { Console.Write(head.Data); if (head.Next != null ) { Console.Write( " <-> " ); } head = head.Next; } Console.WriteLine( " -> NULL" ); } static void Main() { // Create the first example doubly linked list: 2 <-> 6 // <-> 3 <-> 8 <-> 11 <-> 23 <-> 7 // Create the nodes Node node1 = new Node(2, null , null ); Node node2 = new Node(6, null , node1); Node node3 = new Node(3, null , node2); Node node4 = new Node(8, null , node3); Node node5 = new Node(11, null , node4); Node node6 = new Node(23, null , node5); Node node7 = new Node(7, null , node6); // Connect the nodes node1.Next = node2; node2.Next = node3; node3.Next = node4; node4.Next = node5; node5.Next = node6; node6.Next = node7; // Set the head of the list Node head = node1; // Print the original list Console.Write( "Original List: " ); PrintList(head); // Move the 4th element to the front MoveKthToFront( ref head, 4); // Print the modified list Console.Write( "Modified List: " ); PrintList(head); } } |
Javascript
// JavaScript code for the above approach: class Node { constructor(data, next, prev) { this .data = data; this .next = next; this .prev = prev; } } // Function to move the Kth element to the front of the doubly linked list. function moveKthToFront(head, K) { // Invalid input or K is 1 if (!head || K < 1 || K === 1) { return ; } let current = head; let prevKth = null ; for (let i = 1; i < K && current !== null ; i++) { prevKth = current; current = current.next; } // K is greater than the length of the list if (current === null ) { return ; } // Adjust pointers to bypass the Kth node if (prevKth !== null ) { prevKth.next = current.next; } if (current.next !== null ) { current.next.prev = prevKth; } // Make the Kth node the new head current.next = head; head.prev = current; current.prev = null ; head = current; } // Function to print the doubly linked list. function printList(head) { while (head !== null ) { process.stdout.write(head.data.toString()); if (head.next !== null ) { process.stdout.write( " <-> " ); } head = head.next; } console.log( " -> NULL" ); } // Driver code // Create the first example doubly linked list: 2 <-> 6 <-> 3 <-> 8 <-> 11 <-> 23 <-> 7 // Create the nodes let node1 = new Node(2, null , null ); let node2 = new Node(6, null , node1); let node3 = new Node(3, null , node2); let node4 = new Node(8, null , node3); let node5 = new Node(11, null , node4); let node6 = new Node(23, null , node5); let node7 = new Node(7, null , node6); // Connect the nodes node1.next = node2; node2.next = node3; node3.next = node4; node4.next = node5; node5.next = node6; node6.next = node7; // Set the head of the list let head = node1; // Print the original list process.stdout.write( "Original List: " ); printList(head); // Move the 4th element to the front moveKthToFront(head, 4); // Print the modified list process.stdout.write( "Modified List: " ); printList(head); // This code is contributed by guptapratik |
Original List: 2 <-> 6 <-> 3 <-> 8 <-> 11 <-> 23 <-> 7 -> NULL Modified List: 8 <-> 2 <-> 6 <-> 3 <-> 11 <-> 23 <-> 7 -> NULL
Time Complexity: O(N) due to the traversal of the list, where N is the number of elements.
Auxiliary Space: O(1) as we are not using any extra space.
Contact Us