1721. Swapping Nodes in a Linked List - Explanation

Problem Link



1. Convert To Array

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        arr = []
        cur = head
        while cur:
            arr.append(cur.val)
            cur = cur.next

        n = len(arr)
        arr[k - 1], arr[n - k] = arr[n - k], arr[k - 1]

        cur, i = head, 0
        while cur:
            cur.val = arr[i]
            cur = cur.next
            i += 1

        return head

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(n)O(n)

2. Recursion

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        left, right, startIdx = None, None, 0

        def dfs(node):
            nonlocal left, right, startIdx
            if not node:
                return 0

            startIdx += 1
            if startIdx == k:
                left = node

            endIdx = dfs(node.next) + 1
            if endIdx == k:
                right = node

            return endIdx

        dfs(head)
        if left and right:
            left.val, right.val = right.val, left.val

        return head

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(n)O(n) for recursion stack.

3. Iteration (Two Pass)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        n = 0
        cur = head
        while cur:
            n += 1
            cur = cur.next

        left, right = None, None
        cur = head
        for i in range(1, n + 1):
            if i == k:
                left = cur
            if i == (n - k + 1):
                right = cur
            cur = cur.next

        left.val, right.val = right.val, left.val
        return head

Time & Space Complexity

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

4. Iteration (One Pass) - I

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        cur = head
        for _ in range(k - 1):
            cur = cur.next

        left = cur
        right = head

        while cur.next:
            cur = cur.next
            right = right.next

        left.val, right.val = right.val, left.val
        return head

Time & Space Complexity

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

5. Iteration (One Pass) - II

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        left, right = None, None
        cur = head

        while cur:
            if right:
                right = right.next
            if k == 1:
                left = cur
                right = head
            k -= 1
            cur = cur.next

        left.val, right.val = right.val, left.val
        return head

Time & Space Complexity

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