Swapping Nodes in a Linked List

TARGET DECK: Leetcode FILE TAGS:

Intuition

• It asks to swap the kth and n-kth value.
• In 2 passes, we can get the kth Node and n - k + 1th node
  • The reason it is + 1 is because we want the node k away from the end, so k = 1 going backwards would be the 1st node going forwards.
• In 1 pass, we can note that finding the n - k + 1th node reduces to starting the endNode at the beginning after you have found the kth node and then traversing until complete.
  • This works because kth node is k - 1 nodes from head, so we want k - 1 nodes from the last node.

Cards

START Basic Front: Swapping Nodes in a Linked List - LeetCode Back: kth node is k - 1 nodes from head, so we want k - 1 nodes from the last node. Similar to Floyds Tortoise and Hare

END

Complexity

Runtime

$O(N)$

Space

$O(1)$

Code

1 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]:        
        count = 0
        itr = head
        kthNode = None
        nMinusKthNode = None
        placed = False
        while itr:
            if placed:
                nMinusKthNode = nMinusKthNode.next
                
            count += 1
            if count == k:
                placed = True
                kthNode = itr
                nMinusKthNode = head
            itr = itr.next
        
        kthNode.val, nMinusKthNode.val = nMinusKthNode.val, kthNode.val
 
        return head

2 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]:
        # Get count
        itr = head
        n = 0
        while itr:
            n += 1
            itr = itr.next
        
        count = 0
        itr = head
        kthNode = None
        nMinusKthNode = None
        while itr:
            count += 1
            if count == k:
                kthNode = itr
            if count == n - k + 1:
                nMinusKthNode = itr
            itr = itr.next
        
        kthNode.val, nMinusKthNode.val = nMinusKthNode.val, kthNode.val
 
        return head

Notes

---

References

Swapping Nodes in a Linked List - LeetCode