How to reverse K alternate nodes in a singly linked list

A singly linked list is a collection of data stored in nodes, each connected to the next using a pointer.

Note: We can read more about singly linked lists here.

To reverse $\text{K}$ alternate elements in a singly linked list, where $\text{K}$ is an integer, we first need to reverse the first $\text{K}$ elements, traverse past the next $K$ elements, and then repeat these steps using a recursive approach.

Illustration

As an example, let's look at the following singly linked list:

reverseKAlternate.py

linkedList.py

import linkedList
def reverseKAlternate(k, head): 
    current = head # used to traverse the linked list
    next = None # used to change the next pointers when reversing nodes
    new_head = None # stores the head of the final linked list
    count = 0 # used to ensure we reverse at every K alternate nodes
  
    while count < k and current != None:
        count += 1
        next = current.next
        current.next = new_head 
        new_head = current 
        current = next
      
    if head != None: 
        head.next = current 
  
    count = 0
    while count < k - 1 and current != None:
        count += 1
        current = current.next
       
    if current != None: 
        current.next = reverseKAlternate(k, current.next) 
   
    return new_head 
K = 2
original_list = linkedList.linkedList()
original_list.insert(1) 
original_list.insert(2) 
original_list.insert(3) 
original_list.insert(4)
original_list.insert(5)
original_list.insert(6) 
original_list.insert(7) 
original_list.insert(8) 
original_list.insert(9) 
original_list.insert(10)  
print("Original Linked List:", end = ' ')
original_list.printList()
print()
final_list = linkedList.linkedList()
final_list.head = reverseKAlternate(K, original_list.head)
print("Final Linked List:", end = ' ')
final_list.printList()

Note: We can edit the value of $\text{K}$ in line 31.

Explanation

The file linkedList.py contains the definition of the linked list and node class, along with a few helper functions.

The following is happening in the reverseKAlternate.py file:

Lines 3–28: The function reverseKAlternate(k, head) takes in a value for the number of alternating nodes k along with the head of the original linked list stored in head.
Lines 9–14: We reverse the first k nodes of the linked list. The value count ensures we only reverse k nodes.
Lines 16–17: The value current is now the (k+1)^th element of the linked list, so the next element after the head node will be current.
Lines 19–23: The next k elements do not have to be reversed, so we simply traverse past them.
Lines 25–26: We replicate the code in lines 9–23 for the rest of the list, starting at current.next (since current is the 2k^thelement), by calling reverseKAlternate() recursively.
Line 31: We store the number of alternating nodes in the variable K.
Lines 35–44: We create the original linked list by inserting its nodes individually.
Lines 46–48: We print the original linked list.
Lines 50–54: We call the function reverseKAlternate() and print the final linked list.

How to reverse K alternate nodes in a singly linked list

Illustration

Implementation

Explanation