leetcode/24_swap_nodes_in_pairs

24_swap_nodes_in_pairs

dz / leetcode / 24_swap_nodes_in_pairs

Summary

24. Swap Nodes in Pairs. Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)

Node Tree

Nodes

URL
content URL
hyperlink https://leetcode.com/problems/swap-nodes-in-pairs

intuition
content This is another linked list manipulation problem. It's more about getting the details right. I've stated this before, but I'm not a fan of these kinds of problems in coding interviews because it can be easy to miss the details in a stressful situation. The gist of this comes down updating pointer values in a loop. Drawing a picture and visualizing this is best in my experience.
children visualize, approach_2_iteration (This is the approach I thought up.)

visualize
content A->B->C->D becomes B->A->D->C. Swapping happens in pairs two at a time, so the intermediate lists would look like B->A->C->D, then B->A->D->C.
parents intuition

swap_algo
content Run while value "node" is not null. Let A = node, B = node.next. Update current node. node = B.next. Swap: update B.next = A. Clear A next: A.next = NULL. Update previous node, if not null: prev.next = A. Update previous node: prev = A.
children working_out (working out this algorithm)

working_out
content Working out this algo. A->B->C->D. B->A->NULL C->D. node=C, prev=A. B->A->NULL, D->C->NULL. B->A->D->C. node=NULL, prev=C. END.
children approach_2_iteration (worked out my algorithm after reading this one to make sure mine works. I think it does?)
parents swap_algo

editorial
content editorial
children approach_2_iteration, approach_1_recursion

approach_1_recursion
content Approach 1 uses recursion. As an input it takes in a head, and it returns a new head. Base case is when the head is null, meaning it has reached the end of the list. Each call swaps the two nodes, and returns the new head. Head and head->next make A, B. A.next = swap(B.next), and B.next = A.
parents editorial

approach_2_iteration
content This was basically the approach I came up with. In my algorithm, I cleared the pointer of the value and waited until the next iteration to update it (the last iteration would leave it empty, making it the end of the list). Using my notation, this algorithm does this: A.next = B.next, B.next=A. prev.next=B.
children working_out_approach_2, dummy_node (lots of dummy nodes used in linked list ops)
parents intuition, editorial, working_out

working_out_approach_2
content Working out the iterative approach. A->B->C->D. A->C->D. B->A->C->D. B->A->C->NULL. B->A->C, D->C. B->A->D->C.
parents approach_2_iteration

dummy_node
content They sure do like to use dummy nodes in these solutions will probably need to study this. Maybe this is just to avoid NULL checks?
parents approach_2_iteration