Given a linked list, write a function to reverse every alternate k nodes (where k is an input to the function) in an efficient way. Give the complexity of your algorithm.
Example:
Inputs: 1->2->3->4->5->6->7->8->9->NULL and k = 3 Output: 3->2->1->4->5->6->9->8->7->NULL.
Method 1 (Process 2k nodes and recursively call for rest of the list):
This method is basically an extension of the method discussed in this post.
kAltReverse(struct node *head, int k)
1) Reverse first k nodes.
2) In the modified list head points to the kth node. So change next
of head to (k+1)th node
3) Move the current pointer to skip next k nodes.
4) Call the kAltReverse() recursively for rest of the n - 2k nodes.
5) Return new head of the list.
Java
// Java program to reverse alternate k// nodes in a linked listclass LinkedList{ static Node head; class Node { int data; Node next; Node(int d) { data = d; next = null; } } /* Reverses alternate k nodes and returns the pointer to the new head node */ Node kAltReverse(Node node, int k) { Node current = node; Node next = null, prev = null; int count = 0; / *1) reverse first k nodes of the linked list */ while (current != null && count < k) { next = current.next; current.next = prev; prev = current; current = next; count++; } /* 2) Now head points to the kth node. So change next of head to (k+1)th node*/ if (node != null) { node.next = current; } /* 3) We do not want to reverse next k nodes. So move the current pointer to skip next k nodes */ count = 0; while (count < k - 1 && current != null) { current = current.next; count++; } /* 4) Recursively call for the list starting from current->next. And make rest of the list as next of first node */ if (current != null) { current.next = kAltReverse(current.next, k); } /* 5) prev is new head of the input list */ return prev; } void printList(Node node) { while (node != null) { System.out.print(node.data + " "); node = node.next; } } void push(int newdata) { Node mynode = new Node(newdata); mynode.next = head; head = mynode; } public static void main(String[] args) { LinkedList list = new LinkedList(); // Creating the linkedlist for (int i = 20; i > 0; i--) { list.push(i); } System.out.println("Given Linked List :"); list.printList(head); head = list.kAltReverse(head, 3); System.out.println(""); System.out.println("Modified Linked List :"); list.printList(head); }}// This code is contributed by Mayank Jaiswal |
Output:
Given linked list 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Modified Linked list 3 2 1 4 5 6 9 8 7 10 11 12 15 14 13 16 17 18 20 19
Time Complexity: O(n)
Method 2 (Process k nodes and recursively call for rest of the list):
The method 1 reverses the first k node and then moves the pointer to k nodes ahead. So method 1 uses two while loops and processes 2k nodes in one recursive call.
This method processes only k nodes in a recursive call. It uses a third bool parameter b which decides whether to reverse the k elements or simply move the pointer.
_kAltReverse(struct node *head, int k, bool b)
1) If b is true, then reverse first k nodes.
2) If b is false, then move the pointer k nodes ahead.
3) Call the kAltReverse() recursively for rest of the n - k nodes and link
rest of the modified list with end of first k nodes.
4) Return new head of the list.
Java
// Java program to reverse alternate// k nodes in a linked listclass LinkedList{ static Node head; class Node { int data; Node next; Node(int d) { data = d; next = null; } } /* Alternatively reverses the given linked list in groups of given size k. */ Node kAltReverse(Node head, int k) { return _kAltReverse(head, k, true); } /* Helper function for kAltReverse(). It reverses k nodes of the list only if the third parameter b is passed as true, otherwise moves the pointer k nodes ahead and recursively calls itself */ Node _kAltReverse(Node node, int k, boolean b) { if (node == null) { return null; } int count = 1; Node prev = null; Node current = node; Node next = null; /* The loop serves two purposes 1) If b is true, then it reverses the k nodes 2) If b is false, then it moves the current pointer */ while (current != null && count <= k) { next = current.next; /* Reverse the nodes only if b is true*/ if (b == true) { current.next = prev; } prev = current; current = next; count++; } /* 3) If b is true, then node is the kth node. So attach the rest of the list after the node. 4) After attaching, return the new head */ if (b == true) { node.next = _kAltReverse(current, k, !b); return prev; } /* If b is not true, then attach rest of the list after prev. So attach rest of the list after prev */ else { prev.next = _kAltReverse(current, k, !b); return node; } } void printList(Node node) { while (node != null) { System.out.print(node.data + " "); node = node.next; } } void push(int newdata) { Node mynode = new Node(newdata); mynode.next = head; head = mynode; } // Driver code public static void main(String[] args) { LinkedList list = new LinkedList(); // Creating the linkedlist for (int i = 20; i > 0; i--) { list.push(i); } System.out.println("Given Linked List :"); list.printList(head); head = list.kAltReverse(head, 3); System.out.println(""); System.out.println("Modified Linked List :"); list.printList(head); }}// This code is contributed by Mayank Jaiswal |
Output:
Given linked list 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Modified Linked list 3 2 1 4 5 6 9 8 7 10 11 12 15 14 13 16 17 18 20 19
Time Complexity: O(n)
Auxiliary Space: O(n) For call stack because it is using recursion
Please refer complete article on Reverse alternate K nodes in a Singly Linked List for more details!
