Good morning! Here's our prompt for today.

Write a recursive algorithm that swaps every two nodes in a linked list. This is often called a pairwise swap. For example:

1/*
2original list
31 -> 2 -> 3 -> 4
4
5after swapping every 2 nodes
62 -> 1 -> 4 -> 3
7*/

You may assume that the definition of a linked list node is:

1function Node(val) {
2  this.value = val;
3  this.next = null;
4}

The method will be invoked as such after setup:

1const list = new Node(1);
2list.next = new Node(2);
3list.next.next = new Node(3);
4list.next.next.next = new Node(4);
5
6swapEveryTwo(list);

Constraints

• Length of the linkedlist <= 100000
• The nodes will always contain integer values between -1000000000 and 1000000000
• The list can be empty
• Expected time complexity : O(n)
• Expected space complexity : O(n)

Note: The strength of linked lists is that you can dynamically add or remove any nodes within a constant time, given the address of the node. This is not possible in arrays or a sequential memory holding data structure. Each node in a linked list is created dynamically on the heap section of the memory. For this reason, you can create a very large Linked List (most probably larger than an array of the same size) as long as you have a memory to allocate. Creating more nodes than your memory can store will result in a heap overflow.

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

xxxxxxxxxx

​

def swap_every_two(head):

    # fill in this method

    return head

​

​

# Node definition

class Node:

    def __init__(self, val):

        self.val = val

        self.next = None

​

​

def create_nodes(head, nodes):

    for val in nodes:

        new_node = Node(val)

        head.next = new_node

        head = new_node

​

​

list1 = Node(3)

nodes1 = [4, 5, 6, 7, 8, 9, 10]

create_nodes(list1, nodes1)

​

list2 = Node(1)

nodes2 = [2, 3, 4, 5, 6, 7, 8]

create_nodes(list2, nodes2)

​

​

def list_to_str(head):

Here's our guided, illustrated walk-through.

How do I use this guide?