1721. Swapping Nodes in a Linked List

1721. Swapping Nodes in a Linked List

Tag: Linked List Two Pointers

Difficulty: Medium

You are given the head of a linked list, and an integer k.

Return the head of the linked list after swapping the values of the k^th node from the beginning and the k^th node from the end (the list is 1-indexed).

---

Example 1:

Input: head = [1,2,3,4,5], k = 2
Output: [1,4,3,2,5]

Example 2:

Input: head = [7,9,6,6,7,8,3,0,9,5], k = 5
Output: [7,9,6,6,8,7,3,0,9,5]

Constraints:

• The number of nodes in the list is n.
• 1 <= k <= n <= 10^5
• 0 <= Node.val <= 100

---

Approach 1: Three Pass

• Time Complexity: O(n), where n is the length of the Linked List. We are iterating over the Linked List thrice.
• Space Complexity: O(1)

# 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]:
        def get_size(node):
            if not node:
                return 0
            size = 0
            while node:
                size += 1
                node = node.next
            return size
        
        size = get_size(head)
        left = right = 0
        lprev = rprev = head

        while left < k - 1:
            left += 1
            lprev = lprev.next

        while right < size - k:
            right += 1
            rprev = rprev.next

        lprev.val, rprev.val = rprev.val, lprev.val
        return head

Approach 2: Two Pass

• Time Complexity: O(n), where n is the length of the Linked List. We are iterating over the Linked List twice.
• Space Complexity: O(1)

# 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]:
        def get_size(node):
            if not node:
                return 0
            size = 0
            while node:
                size += 1
                node = node.next
            return size
        
        size = get_size(head)
        left = right = 0
        lprev = rprev = head

        while left < k - 1 or right < size - k:
            if left < k - 1:
                left += 1
                lprev = lprev.next
            if right < size - k:
                right += 1
                rprev = rprev.next
        
        lprev.val, rprev.val = rprev.val, lprev.val
        return head

---

Follow up question: swap the nodes instead of the values

# 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]:
        def get_size(node):
            if not node:
                return 0
            size = 0
            while node:
                size += 1
                node = node.next
            return size

        size = get_size(head)
        left = right = 0
        sentinel = fast = slow = curr = ListNode(next=head)

        while left < k - 1 or right < size - k:
            if left < k - 1:
                left += 1
                slow = slow.next
            if right < size - k:
                right += 1
                fast = fast.next

        if slow != fast:
            slow.next, fast.next = fast.next, slow.next
            slow.next.next, fast.next.next = fast.next.next, slow.next.next

        return sentinel.next

# 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]:
        sentinel = fast = slow = curr = ListNode(next=head)

        while k > 1:
            k -= 1
            slow = slow.next    # Now slow is the prev node of the kth node.

        curr = slow.next.next
        while curr:
            fast = fast.next    # Now fast is the prev node of the -kth node.
            curr = curr.next  

        if slow != fast:
            slow.next, fast.next = fast.next, slow.next
            slow.next.next, fast.next.next = fast.next.next, slow.next.next

        return sentinel.next