Skip to main content

1721 - Swapping Nodes in a Linked List.

Hi, Today we will be solving leetcode qs 1721 - Swapping Nodes in a Linked List.

This qs is really simple. We need to swap the nodes placed at k distance from the start and end of the Linked List. So let's suppose you have a Linked List input as follows:

1 -> 2-> 4 -> 5 -> 7 -> 8 -> 10-> 9

 and you are given a k = 2, so the output should be

1 -> 10-> 4 -> 5 -> 7 -> 8 ->2 -> 9

so how do we achieve it???

Intuition

The most brute force solution one can think of is using Array data structure. For that, we will traverse through linked List and store all the elements in the Array, swap the two numbers and again insert it in theLinked List again. Not bad, but let's deal with it, it is not the optimal solution and far from being as an acceptable solution in interviews.

So what can we done instead of that???

Let's try to look deep into the working of Linked List first and how do we traverse it. Linked List is a linear data structure that consists of a value and a next pointer.

This is how we initiate a LinkedList Node:


class LinkedList:
def __init__(self, val):
self.val = val
self.next = None


Here val is the value stored in Linked List and next is the pointer that is used to point to next Node. Currently it is pointing to None.

So in general to access the Linked List Nodes we use pointers. The first node in the linked list is defined as the head and last element is defined as tail. The tail nodes points to None defining that Linked List has ended.

So coming back to the qs, We know that we will be using pointers, here as we need two values kth value from start and end ,  we will be using concept of two pointers

Approach

We will make sure to move a pointer to the point of k and call it firstNode and then iterate over linked list again but this time second pointer secondNode will start from head and our first created pointer will start from its own place which we got from first iteration. and in this iteration we will move our firstNode till the last node of head. This is because when firstNode will hit the last  we will get the secondNode.


firstNode postion = k-1

secondNode position = count -k


Note: To keep the node position in check we will assign another pointer to firstNode and will be moving that in second iteration

Complexity

Space Complexity = O(1)
Time Complexity = O(N)

N is length of the linked list



Solution


class Solution:
def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
if head is None:
return

firstNode = head

for i in range(1, k):
firstNode=firstNode.next

current = firstNode
secondNode = head

while current.next:
secondNode=secondNode.next
current = current.next

firstNode.val, secondNode.val = secondNode.val, firstNode.val

return head



Link to the qs in leetcode.
Labels:

Comments

Post a Comment

Popular posts from this blog

1235. Maximum Profit in Job Scheduling

Hi everyone, Today's post is little bit intriguing to me as it took me some time to get t the solution. I have been out of practice for a bit so I was not able to do it in the DP. I didn't want to copy the code. Though i understood the code after i checked its solution in the discussions. Anyways, i tried to do it with heap and with some thinking I was able to do it and with my surprise It performed real well. I would like to jump to the solution but first I would like to explain a little bit about heaps so you can get better understanding of the code. A heap is like a special type of list where the smallest (or largest) item is always at the front. Think of it like a priority line at a theme park, where the person with the highest priority goes to the front. There are two types of heaps: Min Heap: The smallest item is at the front. It's like standing in a line where the shortest person is always at the front. Max Heap: The largest item is at the front. It's like stand...
2 comments
Read more

What is a Processor?

Smartphones have been the most important part of our lives. We have seen the evolution of our  handsets. First we saw landlines which were mess of tangled wires then we saw mobile phones which is successor of landlines. They were portable devices from which you can make calls then we witnessed emergence of Smartphones which were  considered as portable computers which also allows us to make calls. What is a Processor? Underneath that touchscreen display there is a full- fledged computer that commands your apps so that they function properly. A processor executes what you want your smartphone to do or in other word you can say processor is brain of computer. there is Exynos, Snapdragon, quad-core octa-core etc. What is a core? It is an element of surprises. They are present inside processor and are responsible for reading the command and executing them. First devices came with single core processor but later on scientists invented more advanced processors such as dual core , So...
Post a Comment
Read more

Group Anagrams – Python Solution Explained

Problem Overview The Group Anagrams problem is a common challenge in coding interviews and competitive programming. The goal is to group a list of strings such that all anagrams are placed in the same group. Anagrams are words that contain the same characters but in different orders. For example, given the input ["eat", "tea", "tan", "ate", "nat", "bat"] , the expected output is [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']] . Approach and Solution In this blog post, we'll discuss an efficient solution using Python's built-in data structures. The provided code uses a dictionary to group the anagrams. Here’s a step-by-step explanation of the approach: Code Breakdown Explanation Initialization: We use defaultdict from the collections module to create a dictionary ( hm ) where each key will map to a list of anagrams. This is useful because it automatically initializes ...
Post a Comment
Read more