LeetCode 24 - Swap Nodes in Pairs (Explanation and Visualization of the code)

Question

/** 
 * Definition for singly-linked list. 
 * struct ListNode { 
 *     int val; 
 *     struct ListNode *next; 
 * }; 
 */ 

struct ListNode* swapPairs(struct ListNode* head){ 

    if(!head || !head -> next) 
        return head; 

    struct ListNode *newHead = head -> next; 
    head -> next = swapPairs(newHead -> next); 
    newHead -> next = head; 
    return newHead; 

}

Given that a linked list, 1 -> 2 -> 3 -> 4 -> 5, I know that when this linked list enter the function signature, "struct ListNode* swapPairs(struct ListNode* head)", "*newHead" is the node containing value 2, which is the second node of the linked list.

head is the pointer to the first node containing value 1. newHead -> next is the pointer to the node containing value 3 (3rd node).

But why "head -> next = swapPairs(newHead -> next)" returns the node containing value 3, which is the third node of the linked list? I don't get why "swapPairs(newHead -> next)" can make "head -> next" point to the third node of the linked list.

I expected that "swapPairs(newHead -> next)" will return a linked list pointer, with a linked list 4 -> 3 -> 5" to "head -> next".

I thought it will return the node containing value 4 and all the pair nodes are swapped after the second node of the linked list.

Please format your question properly. Indent code blocks by 4 characters. — n. m. could be an AI
– n. m. could be an AI, Commented Oct 15, 2023 at 6:44
The best explanation comes from you drawing out the operations on a piece of paper and explaining it to your rubber duck: meta.stackoverflow.com/a/281271/17592432 — user17592432
– user17592432, Commented Oct 15, 2023 at 6:45
But why "head -> next = swapPairs(newHead -> next)" returns the node containing value 3 How do you know? Please post what you directly observe, not what you deduce. A minimal reproducible example would be the best way to convey this information. — n. m. could be an AI
– n. m. could be an AI, Commented Oct 15, 2023 at 7:16

storsan · Accepted Answer · 2023-11-29 12:26:50Z

The code will work as expected.

Taking your case of the singly linked list 1->2->3->4->5 as example, the final result of the processing in the function swapPairs() will make the list as 2->1->4->3->5.

Inside the function swapPairs() , for each pair of nodes, consider that head is the pointer to the old head node (i.e the first node in the pair) and newHead is to become the pointer to the new head node (i.e the second node in the pair) of the to-be-swapped pair.

swapPairs() is called for every adjacent pair of nodes in the entire list and this function returns the first node of the swapped pair which needs to be assigned as the next pointer to the old head node of the previous pair which is yet to be swapped.

A walk through:

For the very first call of the function swapPairs(), head will be pointing to 1 and newHead pointing to 2.

On the second call (recursive) to swapPairs(), head will be pointing to 3 and newHead pointing to 4.

On the third call (recursive), head will be pointing to 5 and head->next is NULL. head being NULL or head->next being NULL is the base case which causes the recursion to stop as per this code:

if(!head || !head -> next) 
        return head;

When this third call returns the old head (5) to it's caller, in the caller head->next of the old head node of the to-be-swapped pair ( 3 and 4) in the caller will be now set to 5.This causes the node 3 to now point to 5:

head -> next = swapPairs(newHead -> next);

newHead which is pointing to 4 will be set to point to the old head node (3) as per the code:

newHead -> next = head; 
    return newHead;

The swap of nodes 3 and 4 is complete. And 4 (as pointed to by newHead) will be returned back to the previous swapPairs() call.

Now when we are back to the very first call of swapPairs(): the old head (pointing to 1) will be set to point to 4 which was returned as the first node of the pair (3,4) from the first recursive invocation of swapPairs() while newHeadis pointing to 2. All that remains is to make newHead->next point to 1 now, thus swapping of 1 and 2 is now completed , then return the pointer newHead (pointing to to 2) back to main() or any other caller that called swapPairs() on the entire linked list.

Collectives™ on Stack Overflow

LeetCode 24 - Swap Nodes in Pairs (Explanation and Visualization of the code)

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related