Skip to main content

Reverse Alternate nodes

Problem Statement

Given a linked list, reverse alternate nodes and append at the end

Walkthrough

Approach

The idea is to maintain two linked lists, one list of all odd positioned nodes and other list of all even positioned nodes . Traverse the given linked list which is considered as an odd list or oddly positioned nodes. If the node is even node, remove it from the odd list and add it to the front of even node list. Nodes are added at front to keep the reverse order. Append the even node list at the end of odd node list.

Code

Python Code
class Node:

# Constructor to initialize the node object
def __init__(self, val):
self.val = val
self.next = None


def printList(head):

while head is not None:
print(head.val, '->', end='')
head = head.next

print('None')


def ReverseAltNodes(head):

oddHead, evenHead = head, head.next
curOdd, curEven = oddHead, evenHead

while oddHead.next is None and curEven.next is None:

curOdd.next = curEven.next
curEven.next = curOdd.next

curOdd = curOdd.next
curEven = curEven.next

printList(oddHead)
printList(evenHead)


if __name__ == '__main__':

root = Node(1)
root.next = Node(2)
root.next.next = Node(3)
root.next.next.next = Node(4)
root.next.next.next.next = Node(5)
root.next.next.next.next.next = Node(6)
root.next.next.next.next.next.next = Node(7)
printList(root)
ReverseAltNodes(root)