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

• URL
• editorial
  • approach_1_recursion
  • approach_2_iteration
    • dummy_node
    • working_out_approach_2
• intuition
  • visualize
  • approach_2_iteration
    • dummy_node
    • working_out_approach_2
• swap_algo
  • working_out
    • approach_2_iteration
      • dummy_node
      • working_out_approach_2

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_1_recursion, approach_2_iteration

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	dummy_node (lots of dummy nodes used in linked list ops), working_out_approach_2
parents	working_out, editorial, intuition

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