Swapping the node in the linked list

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]

Example 3:

Input: head = [1], k = 1
Output: [1]

Example 4:

Input: head = [1,2], k = 1
Output: [2,1]

Example 5:

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

Constraints:

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

Approach 1:

Traverse the entire linked list, while traversing , store the values into an array, as swapping is more easier in case of arrays. Now swap the array element at the index position k from the start and end. Now after the swapping , store back the array element into the linked list back.

Time O(n)

Space :O(n)

Approach 2:

Two pointer approach

Now the much more optimized code in terms of time and space. Here we use two pointers ptr2 and temp , that would initially be at head and k+1 th position. We traverse the entire linked list until the temp points to null, with simultaneously moving the ptr2 . At an instant when the temp reaches the end of the linked list , the ptr2 would basically be at kth node from end. Also we have the ptr1 already pointing to the kth node from beginning . Now swap the values of ptr1 and ptr2

def swapNodes(self, head,k):
        if not head:
            return None
        ptr1=head
        while(k>1):
            k-=1
            ptr1=ptr1.next
        ptr2=head
        temp=ptr1.next
        while(temp):
            ptr2=ptr2.next
            temp=temp.next   
        ptr1.val,ptr2.val=ptr2.val,ptr1.val
        return head

Time O(n)

Space :O(1)