# Swap In Pairs

Last updated: 8th Sept, 2020

#### Problem Statement

Given a linked list, swap every two adjacent nodes and return its head.
Example 1:
1 2 3 4
>> 2 1 4 3
Example 2:
2 4 6 3 1 5
>> 4 2 3 6 5 1

Approach:

Input contains a list of elements in a linked list and the expected output can be achieved by using a single linked list. Firstly a class called Node is created, which represents a node of linked list with variables next that acts as a pointer and data used to store elements in it. The method rearrange is used to swap the adjacent nodes in following manner :

- If head or node pointed by head is none return head.
- If head or node pointed by head is none set current node as head and consider 2 nodes at a time and swap their links.

Complexity Analysis :

- Time Complexity- O(n)
- Space Complexity- O(n)

###### Python Code

    # A linked list node
    class Node:
        def __init__(self, data=None, next=None):
            self.data = data
            self.next = next

    # Helper function to print given linked list
    def printList(head):

        ptr = head
        while ptr:
            print(ptr.data, end=" ")
            ptr = ptr.next

        print("")

    # Function to pairwise swap adjacent nodes of a linked list
    def rearrange(head):

        # if list is empty or contains just one node
        if head is None or head.next is None:
            return head

        curr = head
        prev = None

        # consider two nodes at a time and swap their links
        while curr and curr.next:

            temp = curr.next
            curr.next = temp.next
            temp.next = curr

            if prev is None:
                head = temp
            else:
                prev.next = temp

            prev = curr
            curr = curr.next

        return head

    if __name__ == '__main__':

        head = None
        a = list(map(int, input().split()))
        for i in reversed(a):
            head = Node(i, head)
        head = rearrange(head)
        printList(head)