1721. Swapping Nodes in a Linked List

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 kth node from the beginning and the kth 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 <= 105

• 0 <= Node.val <= 100

# 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]:
        # Distance from last and end is same
        first = second = head
        # Move `first` to kth from start
        for index in range(1,k):
            first = first.next
        temp = first
        # Now move from `first` till end and also move second
        # Once `first` hits end second will be at kth from end of list since distance is same
        while temp.next:
            second = second.next
            temp = temp.next
        first.val, second.val = second.val, first.val
        return head
    
    def swapNodesOld(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        arr = []
        while head:
            arr.append(head.val)
            head = head.next
        # (k-1) since it is given as 1-Indexed
        arr[k-1], arr[-k] = arr[-k], arr[k-1]
        new_head = pointer = None
        for num in arr:
            temp = ListNode(num)
            if new_head is None:
                pointer = new_head = temp
            else:
                pointer.next = temp
                pointer = temp
        return new_head