Reverse alternate k nodes in a linked list

Given a pointer to the head of a Singly linked list, our objective is to reverse the linked list in alternate groups of K nodes.
Reversed alternate K nodes in a linked list

Algorithm:

We discussed Reversing a linked list in groups of K nodes in the previous post.

 The logic here is also the same, the only difference is that before the recursive call we traverse K more nodes so that we can skip them.
?
1
2
3
4
5
6
7
8
"""
Perform the skip after reversing the previous k nodes
"""
count = 0
# traverse the k nodes to be skipped
while current is not None and count < k-1:
    current = current.next
    count += 1

Code in Python:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
# Python program to alternately reverse a linked list in group of given size k
 
 
# Node class
class Node:
 
    # Constructor to initialise data and next
    def __init__(self, data=None):
        self.data = data
        self.next = None
 
 
class SinglyLinkedList:
 
    # Constructor to initialise head
    def __init__(self):
        self.head = None
 
    # Function to reverse K nodes of linked list
    def reverse_k_nodes(self, head, k):
        current = head
        next = None
        prev = None
        count = 0
 
        # traverse k nodes ahead reversing the links or until current is not None
        while current is not None and count < k:
            next = current.next
            current.next = prev
            prev = current
            current = next
            count += 1
 
        if head is not None:
            head.next = current
 
        count = 0
        # traverse the k nodes to be skipped
        while current is not None and count < k-1:
            current = current.next
            count += 1
 
        # recursive call to the function to alternate reverse the remaining n-2k nodes
        if current is not None:
            current.next = self.reverse_k_nodes(current.next, k)
 
        # return the new header of the current sublist
        return prev
 
    # Function to Insert data at the beginning of the linked list
    def insert_at_beg(self, data):
        node = Node(data)
        node.next = self.head
        self.head = node
 
    # Function to print the linked list
    def print_data(self):
        current = self.head
        while current is not None:
            print(current.data, '-> ', end='')
            current = current.next
        print('None')
 
linked_list = SinglyLinkedList()
linked_list.insert_at_beg(10)
linked_list.insert_at_beg(9)
linked_list.insert_at_beg(8)
linked_list.insert_at_beg(7)
linked_list.insert_at_beg(6)
linked_list.insert_at_beg(5)
linked_list.insert_at_beg(4)
linked_list.insert_at_beg(3)
linked_list.insert_at_beg(2)
linked_list.insert_at_beg(1)
linked_list.print_data()
# call the reverse k nodes function
linked_list.head = linked_list.reverse_k_nodes(linked_list.head, 3)
# print the reversed list
linked_list.print_data()
 
"""
Outputs:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> None
3 -> 2 -> 1 -> 4 -> 5 -> 6 -> 9 -> 8 -> 7 -> 10 -> None
"""

--
Have any questions or suggestions? Post in the comments below!!

By,
Anubhav Shrimal

Comments

Post a Comment

Popular posts from this blog

Segregate Even Odd value nodes in a linked list

Image
Given the head of a singly linked list, segregate even value nodes with odd value nodes such that all the even value nodes come before all the odd value nodes in the order of their appearance. Segregate Even and Odd value nodes Algorithm: Remember the pivot logic we used in QuickSort ? In QuickSort the pivot value was used to separate all the values which are smaller than pivot towards the left of the pivot and all the values greater than pivot value towards the right of the pivot. We will use a similar logic here. 1. Find the first even value node. 2. Bring this node to the start of the linked list. (Call it pivot) 3. Find the next even value node. 4. Insert this node after the pivot and increment pivot one node ahead. 5. Repeat this until we reach Null or None. The algorithm states to bring the first even value node to the start of the linked list and make a pointer pivot point towards it. Whenever we find an even value node, we need to link the previous node to ...
Keep reading

What is 3 Algorithms Per Week?

Image
What are Algorithms? Google gives us the first result as below when we search the term "Algorithm": Surely I didn’t understand what it really meant the first time I read this, and yet it is a very important part of our lives, especially for the developers. Name any company in the IT sector, from Google, Microsoft, Facebook to Infosys and TCS, every one of them asks questions based on algorithms and data structures in their interviews. Algorithm is nothing but logic or steps to solve a given problem. Be it sorting of numbers in non increasing order or finding the shortest path from your home to your college on Google Maps, algorithms are everywhere. Why know about Data Structures and Algorithms (DSA)? So, why do these tech companies emphasise on learning DSA? In todays fast paced and every growing world speed and space are very important. We want speed to get our google search results quickly, get faster to the destination location and we want space ...
Keep reading

Sorted Array: Binary Search

Image
Binary Search: Binary search is useful when the input array elements are sorted. The algorithm divides the search space into half each time the element to be searched (x) is not found. It uses 3 conditions: 1. If the current element of the array is equal to x, then return the index. 2. Else if the current element of the array is less than x, then x will be present towards the right of the current element (because the array is sorted). 3. Else if the current element of the array is greater than x, then x will be present towards the left of the current element. GeeksForGeeks: Binary Search Example Code in Python 3: # Function for binary search # inputs: sorted array 'arr', key to be searched 'x' # returns: index of the occurrence of x found in arr def binary_search(arr, x): l = 0 r = len(arr) # while the left index marker < right index marker while l < r: # find the index of the middle element mid = int(l + ((r - l...
Keep reading