LC 1721 [M] Swapping Nodes in a Linked List - ALawliet/algorithms GitHub Wiki

# 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: ListNode, k: int) -> ListNode:
        dum = ListNode(-1, head)
        left = dum # start at -1
        right = head
        
        # increment right n times
        # count from k 1..n instead of 0..n
        while k > 1 and right:
            right = right.next
            k -= 1
        first = right
        
        while right:
            right = right.next
            left = left.next
        second = left
        
        first.val, second.val = second.val, first.val
        
        return dum.next # or head

def swapNodes(self, head: ListNode, k: int) -> ListNode:
        right = head
        left = head

        for _ in range(1, k):
            right = right.next
        first = right

        while right.next:
            right = right.next
            left = left.next
        last = left

        first.val, last.val = last.val, first.val

        return head