Nerd For Tech
Published in

Nerd For Tech

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

Photo by Garmin Bao on Unsplash

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 = 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

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.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store