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)