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