Move the Kth Element in a Doubly Linked List to the End
Given a doubly linked list and an integer K, you need to move the Kth element to the end of the list while maintaining the order of the other elements.
Examples:
Input: DLL: 2 <-> 6 <-> 3 <-> 8 <-> 11 <-> 23 <-> 7 -> NULL, K = 1
Output: 6 <-> 3 <-> 8 <-> 11 <-> 23 <-> 7 <-> 2 -> NULL
Explanation: We move the 1st element (with value 2) to the end of the list while preserving the order of other elements.Input: DLL: 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 6 -> NULL, K = 3
Output: 1 <-> 2 <-> 4 <-> 5 <-> 6 <-> 3 -> NULL
Explanation: we move the 3rd element (with value 3) to the end of the list, maintaining the order of other elements.
Approach: To solve the problem follow the below idea:
To reposition the Kth element to the end of a doubly linked list while preserving the order of other elements, we follow a systematic procedure.
- First, we address the special case when K is equal to 1, as the first element lacks a previous node. In this case, we detach the first element from the list and relocate it to the end while updating the head pointer.
- For K values greater than 1, we traverse the list to find the Kth element, keeping track of its previous node. If K exceeds the list’s length, the function exits without changes.
- Next, we adjust the pointers of nodes around the Kth element to bypass it, effectively removing it from its current position in the list.
- Finally, we place the Kth element at the end of the list by updating its pointers to connect with the last node. This approach efficiently handles various scenarios, ensuring that the Kth element is moved to the end while maintaining the order of the remaining elements.
Steps of the approach:
- Check for invalid input: Ensure the doubly linked list is not empty and K is a positive integer.
- Special handling for K = 1: If K is 1, move the first element to the end and update the head pointer.
- 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 element and remove it from its current position.
- Find the last element in the list using a loop.
- Make the Kth element the new last element by updating pointers.
- Ensure the bidirectional linkage between the Kth element and the previous last element.
- Update the last element’s next pointer to connect it to the Kth element.
- Set the Kth element’s next pointer to null, making it the new last element in the list.
Below is the implementation for the 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 end of the doubly linked list. void moveKthToEnd(Node*& head, int K) { if (head == nullptr || K < 1) { return ; // Invalid input } Node* current = head; Node* prevKth = nullptr; if (K == 1) { // Special case for moving the // first element to the end Node* newHead = head->next; head->prev = nullptr; Node* tail = head; while (tail->next) { tail = tail->next; } tail->next = current; current->prev = tail; current->next = nullptr; head = newHead; return ; } 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; } // Move the Kth node to the end Node* tail = head; while (tail->next) { tail = tail->next; } tail->next = current; current->prev = tail; current->next = nullptr; } // 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 5th element to the end moveKthToEnd(head, 1); // Print the modified list cout << "Modified List: "; printList(head); return 0; } |
Java
class Node { int data; Node next; Node prev; Node( int val) { data = val; next = null ; prev = null ; } } public class Main { // Function to move the Kth element to the end of the doubly linked list static void moveKthToEnd(Node head, int K) { if (head == null || K < 1 ) { return ; // Invalid input } Node current = head; Node prevKth = null ; if (K == 1 ) { // Special case for moving the first element to the end Node newHead = head.next; head.prev = null ; Node tail = head; while (tail.next != null ) { tail = tail.next; } tail.next = current; current.prev = tail; current.next = null ; head = newHead; return ; } 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; } // Move the Kth node to the end Node tail = head; while (tail.next != null ) { tail = tail.next; } tail.next = current; current.prev = tail; current.next = null ; } // 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" ); } 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 ); Node node2 = new Node( 6 ); Node node3 = new Node( 3 ); Node node4 = new Node( 8 ); Node node5 = new Node( 11 ); Node node6 = new Node( 23 ); Node node7 = new Node( 7 ); // Connect the nodes node1.next = node2; node2.next = node3; node3.next = node4; node4.next = node5; node5.next = node6; node6.next = node7; node2.prev = node1; node3.prev = node2; node4.prev = node3; node5.prev = node4; node6.prev = node5; node7.prev = node6; // Set the head of the list Node head = node1; // Print the original list System.out.print( "Original List: " ); printList(head); // Move the 2nd element to the end moveKthToEnd(head, 2 ); // Print the modified list System.out.print( "Modified List: " ); printList(head); } } |
Python3
class Node: def __init__( self , val): self .data = val self . next = None self .prev = None # Function to move the Kth element to the end of the doubly linked list def moveKthToEnd(head, K): if head is None or K < 1 : return # Invalid input current = head prevKth = None if K = = 1 : # Special case for moving the first element to the end newHead = head. next head.prev = None tail = head while tail. next is not None : tail = tail. next tail. next = current current.prev = tail current. next = None head = newHead return for i in range ( 1 , K): if current is not None : prevKth = current current = current. next # K is greater than the length of the list if current is None : return # Adjust pointers to bypass the Kth node if prevKth is not None : prevKth. next = current. next if current. next is not None : current. next .prev = prevKth # Move the Kth node to the end tail = head while tail. next is not None : tail = tail. next tail. next = current current.prev = tail current. next = None # Function to print the doubly linked list def printList(head): while head is not None : print (head.data, end = "") if head. next is not None : print ( " <-> " , end = "") head = head. next print ( " -> NULL" ) node1 = Node( 2 ) node2 = Node( 6 ) node3 = Node( 3 ) node4 = Node( 8 ) node5 = Node( 11 ) node6 = Node( 23 ) node7 = Node( 7 ) node1. next = node2 node2. next = node3 node3. next = node4 node4. next = node5 node5. next = node6 node6. next = node7 node2.prev = node1 node3.prev = node2 node4.prev = node3 node5.prev = node4 node6.prev = node5 node7.prev = node6 # Set the head of the list head = node1 print ( "Original List: " , end = "") printList(head) # Move the 2nd element to the end moveKthToEnd(head, 2 ) print ( "Modified List: " , end = "") printList(head) |
C#
using System; public class Node { public int data; public Node next; public Node prev; public Node( int val) { data = val; next = null ; prev = null ; } } public class MainClass { // Function to move the Kth element to the end of the doubly linked list static void MoveKthToEnd(Node head, int K) { if (head == null || K < 1) { return ; // Invalid input } Node current = head; Node prevKth = null ; if (K == 1) { // Special case for moving the first element to the end Node newHead = head.next; head.prev = null ; Node firstTail = head; while (firstTail.next != null ) { firstTail = firstTail.next; } firstTail.next = current; current.prev = firstTail; current.next = null ; head = newHead; return ; } 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; } // Move the Kth node to the end Node tail = head; while (tail.next != null ) { tail = tail.next; } tail.next = current; current.prev = tail; current.next = null ; } // Function to print the doubly linked list static void PrintList(Node head) { while (head != null ) { Console.Write(head.data); if (head.next != null ) { Console.Write( " <-> " ); } head = head.next; } Console.WriteLine( " -> NULL" ); } 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); Node node2 = new Node(6); Node node3 = new Node(3); Node node4 = new Node(8); Node node5 = new Node(11); Node node6 = new Node(23); Node node7 = new Node(7); // Connect the nodes node1.next = node2; node2.next = node3; node3.next = node4; node4.next = node5; node5.next = node6; node6.next = node7; node2.prev = node1; node3.prev = node2; node4.prev = node3; node5.prev = node4; node6.prev = node5; node7.prev = node6; // Set the head of the list Node head = node1; // Print the original list Console.Write( "Original List: " ); PrintList(head); // Move the 2nd element to the end MoveKthToEnd(head, 2); // Print the modified list Console.Write( "Modified List: " ); PrintList(head); } } |
Javascript
// Definition for a doubly-linked list node. class Node { constructor(data, next, prev) { this .data = data; this .next = next; this .prev = prev; } } // Function to move the Kth element // to the end of the doubly linked list. function moveKthToEnd(head, K) { if (head === null || K < 1) { return ; // Invalid input } let current = head; let prevKth = null ; if (K === 1) { // Special case for moving the // first element to the end let newHead = head.next; head.prev = null ; let tail = head; while (tail.next) { tail = tail.next; } tail.next = current; current.prev = tail; current.next = null ; head = newHead; return ; } for (let i = 1; i < K && current; 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) { prevKth.next = current.next; } if (current.next) { current.next.prev = prevKth; } // Move the Kth node to the end let tail = head; while (tail.next) { tail = tail.next; } tail.next = current; current.prev = tail; current.next = null ; } // Function to print the doubly linked list. function printList(head) { while (head) { console.log(head.data); if (head.next) { console.log( " <-> " ); } head = head.next; } console.log( " -> NULL" ); } // Drivers 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 console.log( "Original List: " ); printList(head); // Move the 5th element to the end moveKthToEnd(head, 1); // Print the modified list console.log( "Modified List: " ); printList(head); |
Original List: 2 <-> 6 <-> 3 <-> 8 <-> 11 <-> 23 <-> 7 -> NULL Modified List: 6 <-> 3 <-> 8 <-> 11 <-> 23 <-> 7 <-> 2 -> NULL
Time Complexity: O(N) due to the traversal of the list, where N is the number of elements.
Space Complexity: O(1) as we are not using any extra space.
Contact Us