24. Swap Nodes in Pairs

Solution 1: Recursive

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        
        revNxt = self.swapPairs(head.next.next)
        newHead = head.next
        newHead.next = head
        head.next = revNxt
        
        return newHead

Time Complexity: O(N)
Space Complexity: O(1)

Solution 2: Iterative

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        
        newHeadAfterReversed = head.next
        pre = None
        cur = head
        nxt = None
        while cur and cur.next:
            nxt = cur.next
            if pre:
                pre.next = nxt
            cur.next = nxt.next
            nxt.next = cur
            
            pre = cur
            cur = cur.next
        
        return newHeadAfterReversed

Time Complexity: O(N)
Space Complexity: O(1)

Solution 3: Dummy Node + Iterative

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        
        dummyNode = ListNode()
        pre = dummyNode
        while head and head.next:
            nxt = head.next
            pre.next = nxt
            head.next = nxt.next
            nxt.next = head
            # Advance ptr for next iteration
            pre = head
            head = head.next
        
        return dummyNode.next

Time Complexity: O(N)
Space Complexity: O(1)

Reference

https://leetcode.com/problems/swap-nodes-in-pairs/discuss/1774318/Python3-I-HATE-LINKED-LISTS-shDsh-Not-Explained

Follow-up 1: 1721. Swapping Nodes in a Linked List

Follow-up 2: 25. Reverse Nodes in k-Group