Published in

Nerd For Tech

# Swapping Nodes in a Linked List — Day 96(Python)

Today’s question is taken from the Daily Leetcode Coding challenge — March edition. Let us look into the problem statement.

1721. Swapping Nodes in a 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 = 2Output: [1,4,3,2,5]`

Example 2:

`Input: head = [7,9,6,6,7,8,3,0,9,5], k = 5Output: [7,9,6,6,8,7,3,0,9,5]`

Example 3:

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

Example 4:

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

Example 5:

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

Constraints:

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

We are given a linked list and an input number “K”. We have to swap the values at the Kth node from the front and the Kth node from the end.

Since we need to swap just the values, we will store the nodes at the Kth position (both from start and end) in a variable and we will swap the values between them.

It is easy to find the Kth node from the start. But how would we know the Kth node from the end? We have a fast pointer and a slow pointer. The fast pointer will keep moving forward until we reach the Kth node. Once we reach the Kth node, we will start moving our slow pointer. At this point, both our fast and slow pointer will keep moving. Once when the fast pointer reaches the end of the linked list, the slow pointer will be pointing to the Kth node from the end of the linked list.

Let us look into the code snippet.

`class NodeSwaper:    def swapNodes(self, head: ListNode, k: int) -> ListNode:        fast_ptr = 1        start = 0        end = head        temp = head        while(temp):            if fast_ptr == k:                start = temp            temp = temp.next            fast_ptr += 1            if fast_ptr > k+1:                end = end.next        start.val, end.val = end.val, start.val        return head`

# Complexity analysis.

Time Complexity

The time complexity is O(N) since we are traversing through our linked list once.

Space Complexity

The space complexity is O(1) since we are not using any other data structure to store calculations.

In the above question, we just had to exchange values. The below code will exchange the whole node itself rather than just the values.

`class NodeSwaper:    def swapNodes(self, head: ListNode, k: int) -> ListNode:        dictionary_ll = dict()        i = 1        temp = head        while(temp):            dictionary_ll[i] = temp            temp = temp.next            dictionary_ll[i].next = None            i += 1        temp = dictionary_ll[k]        dictionary_ll[k] = dictionary_ll[i-k]        dictionary_ll[i-k] = temp        new_head = dictionary_ll[1]        new_head_return = new_head        i = 2        while(i <= len(dictionary_ll)):            new_head.next = dictionary_ll[i]            i += 1            new_head = new_head.next        return new_head_return`

# Complexity analysis.

Time Complexity

The time complexity is O(N) since we are traversing through our linked list once.

Space Complexity

The space complexity is O(N) since we are using a dictionary to store the linked list.

--

--

## More from Nerd For Tech

NFT is an Educational Media House. Our mission is to bring the invaluable knowledge and experiences of experts from all over the world to the novice. To know more about us, visit https://www.nerdfortech.org/.