Swap Nodes in Pairs - Apple Interview Question - Leetcode 24

0:00 - Read the problem
1:25 - Drawing solution
5:15 - Coding solution

leetcode 24

#linkedlist #apple #python

[wlcheng]

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!

[kewtomrao]

Theres no way i am coming up with this logic.
Have solved about 400+ problems, but this level of thing is just too much!

[vdyb]

This is so tricky and yet you have made it look simple !!! Fantastic .... Thank you so very much

[CrazyzzzDudezzz]

Wonderful explanation, if someone asked me to come up with this in 30 minutes I would walk out

[DmitriyKl]

Thank you! This took a couple of rewatches and I had to draw out my own list, but made sense after all!

[orellavie]

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

[gatusko]

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.

[_anshuj]

Why do we use a dummy node and not something like nullptr? (I apologize if i sound stupid)

[yilmazbingol]

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 :)

[WaldoTheWombat]

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

[RGB_]

oh my this problem really fucked up my head last night

[ForCodingInterview]

Thanks NeetCode for the wonderful explanation

[testbot]

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

[Ishaana]

After the first pair of swapping where is the pointer location I mean where is prev, at 1 ???

[maskachung]

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

[Aditya.Rawat]

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_am_acai]

why do we need a dummy node? why not just set directly to the second node and return that?

[LeonLeonLeonardo]

class Solution {
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) return head;

swap(head);
swapPairs(head.next.next);

return head;
}

private void swap(ListNode head) {
int nextValue = head.next.val;
head.next.val = head.val;
head.val = nextValue;
}
}

[halahmilksheikh]

In the drawing, prev is at the head but in the code, prev is at the dummy. Was that a mistake?

[Jia-Tan]

Can't we just use extra memory (array) for a problem like this? Makes it much simpler