Leetcode 24 Solution

This article provides solution to leetcode question 24 (swap-nodes-in-pairs)
Categories:
Tags:
Access this page by simply typing in "lcs 24" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/swap-nodes-in-pairs

Thinking Process

This is a very basic question, although leetcode marks it as medium. Be sure to leverage the dummy head trick to keep the code clean.

Time & Space Complexity

Assuming there are N nodes in the list:

  • Time complexity: O(N)
  • Space complexity: O(1)

Solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        dummyhead = ListNode(None)
        dummyhead.next = head

        def dfs(node, prev):
            if not node or not node.next:
                return

            prev.next = node.next
            node.next = node.next.next
            prev.next.next = node

            dfs(node.next, node)

        dfs(head, dummyhead)
        return dummyhead.next