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.
Python3
# Python3 program to reverse alternate# k nodes in a linked listimport math# Link list node class Node: def __init__(self, data): self.data = data self.next = None# Reverses alternate k nodes and #returns the pointer to the new # head node def kAltReverse(head, k) : current = head next = None prev = None count = 0 # 1) reverse first k nodes of the # linked list while (current != None and count < k) : next = current.next current.next = prev prev = current current = next count = count + 1; # 2) Now head pos to the kth node. # So change next of head to (k+1)th node if(head != None): head.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 and current != None ): current = current.next count = count + 1 # 4) Recursively call for the list # starting from current.next. And make # rest of the list as next of first node if(current != None): current.next = kAltReverse(current.next, k) # 5) prev is the new head of the # input list return prev # UTILITY FUNCTIONS # Function to push a node def push(head_ref, new_data): # Allocate node new_node = Node(new_data) # Put in the data # new_node.data = new_data # Link the old list of the # new node new_node.next = head_ref # Move the head to point to the # new node head_ref = new_node return head_ref# Function to print linked list def printList(node): count = 0 while(node != None): print(node.data, end = " ") node = node.next count = count + 1 # Driver codeif __name__=='__main__': # Start with the empty list head = None # Create a list # 1.2.3.4.5...... .20 for i in range(20, 0, -1): head = push(head, i) print("Given linked list ") printList(head) head = kAltReverse(head, 3) print("Modified Linked list") printList(head) # This code is contributed by Srathore |
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) due to recursive stack space
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.
Python3
# Python code for above algorithm# Link list node class node: def __init__(self, data): self.data = data self.next = next # Function to insert a node at the# beginning of the linked listdef push(head_ref, new_data): # Allocate node new_node = node(0) # Put in the data new_node.data = new_data # Link the old list to the # new node new_node.next = (head_ref) # Move the head to point to the # new node (head_ref) = new_node return head_ref """ Alternatively reverses the given linked list in groups of given size k. """def kAltReverse(head, 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 call itself """def _kAltReverse(Node, k, b) : if(Node == None) : return None count = 1 prev = None current = Node next = None """ 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 != None and count <= k) : next = current.next """ Reverse the nodes only if b is True """ if(b == True) : current.next = prev prev = current current = next count = count + 1 """ 3) If b is True, then node is the kth node. So attach rest of the list after node. 4) After attaching, return the new head """ if(b == True) : Node.next = _kAltReverse(current, k, not b) return prev else : """ If b is not True, then attach rest of the list after prev. So attach rest of the list after prev """ prev.next = _kAltReverse(current, k, not b) return Node """ Function to print linked list """def printList(node) : count = 0 while(node != None) : print( node.data, end = " ") node = node.next count = count + 1# Driver Code# Start with the empty list head = Nonei = 20# Create a list # 1->2->3->4->5...... ->20 while(i > 0 ): head = push(head, i) i = i - 1print("Given linked list ") printList(head) head = kAltReverse(head, 3) print("Modified Linked list ") printList(head) # This code is contributed by Arnab Kundu |
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!
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!
