Teaching Kids Programming – Pairwise Linked List Nodes Swap Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a singly linked list node, swap each pair of nodes and return the new head.

Constraints
n ≤ 100,000 where n is the number of nodes in node
Example 1
Input
node = [0, 1, 3, 4]
Output
[1, 0, 4, 3]

Example 2
Input
node = [1, 2, 3]
Output
[2, 1, 3]

Convert Linked List to List: Pairwise Linked List Swap

For most linked list problems, we can convert (copy) to a list/array, then we can easily perform the pairwise swaps. Then we convert the list/array back to a linked list:

# class LLNode:
#     def __init__(self, val, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def PairwiseLinkedListSwap(self, node):
        data = []
        while node:
            data.append(node.val)
            node = node.next
        
        for i in range(1, len(data), 2):
            data[i], data[i - 1] = data[i - 1], data[i]

        dummy = LLNode(-1)
        head = dummy
        for i in data:
            head.next = LLNode(i)
            head = head.next

        return dummy.next

Time and space complexity is O(N) where N is the number of the nodes in the linked list.

Swap the Values of Nodes

We can follow/walk the link list and swap the values of every two nodes.

# class LLNode:
#     def __init__(self, val, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def PairwiseLinkedListSwap(self, node):
        head = node
        while head and head.next:
            head.val, head.next.val = head.next.val, head.val
            head = head.next.next
        return node

The time complexity is O(N) and the space complexity is O(1).

Reverse the Link

We can reverse the link for every two nodes. To do this, we can first reverse the link for the first two nodes, then then recursively link to the rest.

# class LLNode:
#     def __init__(self, val, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def PairwiseLinkedListSwap(self, node):
        if not node or not node.next:
            return node

        tail = self.solve(node.next.next)
        head = node.next
        head.next = node
        node.next = tail

        return head

Time complexity is O(N). Space complexity is also O(N) due to recursion.

–EOF (The Ultimate Computing & Technology Blog) —