Swap Nodes in Pairs

Problem Id: 24 Difficulty: Medium Tag: Linked List Tag: Recursion


Intuition

To reverse a pair, we would need 3 pointers, prev, curr and after, which looks like something below.

           prev first second
             |    |    |
head -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL

And then, the solution would be straight forward.

Solution


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        head = ListNode(None, head)
        if head.next is None or head.next.next is None:
            return head.next
        prev, first, second = head, head.next, head.next.next

        while True:
            first.next = second.next
            second.next = first
            prev.next = second

            if first.next is None or first.next.next is None:
                break
            prev, first, second = first, first.next, first.next.next

        return head.next