Leetcode - Swapping Nodes in a Linked List (Python)

March 2021 Leetcode Challenge
Leetcode - Swapping Nodes in a Linked List #1721
Difficulty: Medium

[alanreeves]

This video is a life saver. I was trying to solve a similar problem and I never thought to use an array. I wish I had looked it up 4 hours ago.

[dayal]

Actually the constant space solution is not complex at all. Since we can count the length then all we need to do is make a right pointer point to the length - kth spot and a left pointer point to the kth spot. Then just have a variable called tmp store for example the right.val and then do right.val = left.val and left.val = tmp.

Something like this would work:

class Solution:
def swapNodes(self, head: ListNode, k: int) -> ListNode:
#calculate the length of the linked list
n = 0
ptr = head
while ptr:
n += 1
ptr = ptr.next

node_end = n - k
right = head
while node_end > 0:
node_end -= 1
right = right.next

left = head
while k > 1:
k -= 1
left = left.next

tmp = right.val
right.val = left.val
left.val = tmp

return head

[jasonguan]

That’s rly nice and simple. It makes a lot of sense to me while I’m also doing this challenge. Thx!

[jayantdhingra]

Why to return dummy.next in the end ??