I have been watching your solutions for several months and this time I can draw the exactly same solution as you. So fulfilling! Thanks for your great work!
I agree about dummy idea, but it always gonna point to 1 in the example, why it is accepted? dummy stays the same even if prev is changing to curr, but we had to update dummy.next just once to second with a flag or something. Very weird
I was struggling a lot with this problem. More about the description of the problem I was thinking of swapping every two nodes. For example swap 1->2->3->4->5 Swap 1 with 3 and 3 with 5. But in reality was swamping 1 with 2 and change the pointer of those nodes. Man I was so dumb thank you for explanation.
Recursive solution : if not (head and head.next): return head head.next.next, head.next, head = head, self.swapPairs(head.next.next), head.next return head
I am confused why 'dummy["next"]' does not change. Because we assign prev=dummy. Since we both referencing the same memory address, if we mutate "prev", "dummy" will be mutated too. I even tested myself on jupyter, and "dummy.next" changes :)
The nodes are just pointers. So initially, dummy and prev *point* at the same thing. When you do prev = curr, you are telling prev to point to the memory location that curr is pointing to, but dummy is still pointing where it originally was pointing.
This is how I did it: def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]: if head and head.next: first = head previous = ListNode(69) head = head.next # save the second node in "head" for the return statement while first and first.next: # declare second = first.next third = second.next # switch second.next = first first.next = third # connect to previous previous.next = second # save previous previous = first # iterate to next pair first = third return head
Bro, I have solved like 140 questions,but most of the time I'm unable to solve questions even after trying for 30-40 minutes.in the end i have to look at somebody's solution. How do i build my thinking process?how to improve
I'm in the exact same boat as you. take his solution, put it into python tutor, and go line by line, and draw pictures. don't leave a single thing unclear. there are lots of assumptions made.
i think there is a problem in the drawing that is after swaping, the prev is pointed to the second position of the list, which is 1, not 3, and the curr is pointed to the 3 instead of 4, thats why it is confusing
Having a dummy node makes the code easier to write (removes a lot of edge cases that are troublesome to write and think about) which is why a lot of LinkedList question solutions have dummy nodes added to the start of the list. You can do it without the dummy node, but it'll be more complicated code
I did this recursively by calling each pair in the function. I am wondering about the Big O effectiveness. Would this be O (log N) since the function wouldn't be call for every node, but once for every pair?
Since you're doing once for every pair, it would be O(N/2) which is still considered O(N). This is because by calling on each pair, you're just dividing the number of elements by 2.
The nodes are just pointers. So initially, dummy and prev point at the same thing. When you do prev = curr, you are telling prev to point to the memory location that curr is pointing to, but dummy is still pointing where it originally was pointing. I personally name it as "newHead" instead of "dummy". And in most solutions, you do return newHead.next when you want to return the head.
dummy.next finally pointing to 2 is insane. since initially the given head is at 1 and we initialized dummy's next pointer with it.then without updating the dummy.next at least once how could it would be pointing to 2???
You're correct, that solution is most efficient and easiest to implement. But in the problem statement they require that we are not allowed to change the values, i guess we can think of the node values as Read-Only memory.
In this intermediate state, the link between 1 and 2 breaks, and 1 directly points to 3(i.e. nextPair). We get it back in the link by pointing PREV to 2(i.e. second)
