https://leetcode.com/problems/swapping-nodes-in-a-linked-list

Let us just do what is asked in this problem in two stages:

  1. Find n - total number of elements in our linked list, also check when we meet element number k during this traversal and save it result to node l.
  2. During second traversal just do n-k steps and save result to r.

Finally, just change values of nodes l and r.

Complexity: Time complexity is O(n), more specifially we did n + n - k = 2n-k steps when we traverse our list. Space complexity is O(1).

Duscussion Let us compare it with what is probably expected as the best solution here: make k steps using pointer r, put l to head; then continue to traverse both pointers until r will reach end, than l will be in exactly needed place. What is total number of step we done here: It is k + (n-k)*2 = suprise what 2n - k, exactly the same number of steps we do as in simple approach where you do not need to think at all. So, if you get this problem during interview and after providing this solution interviewer say that there is also Two Pointer solution, explain to him that you solution have exaclty the same complexities and working exactly the same. And so-called one-pass solutions and two-pass solutions are the same.

class Solution:
    def swapNodes(self, head, k):
        n = 0
        beg = head
        while beg:
            if n == k-1: l = beg
            beg = beg.next
            n += 1
        
        r = head
        for m in range(n-k):
            r = r.next
                
        l.val, r.val = r.val, l.val
        return head

If you like the solution, you can upvote it on leetcode discussion section: Problem 1721