LeetCode 24 - 成对交换节点（代码解释和可视化）

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; 

} 

假设有一个链表，1 -> 2 -> 3 -> 4 -> 5，我知道当这个链表输入函数签名时，“struct ListNode* swapPairs(struct ListNode* head)”, “*newHead”是包含值2的节点，它是链表的第二个节点。

head 是指向第一个包含值 1 的节点的指针。 newHead -> next 是指向包含值 3 的节点（第三个节点）的指针。

但是为什么“head -> next = swapPairs(newHead -> next)”返回包含值3的节点，即链表的第三个节点？我不明白为什么“swapPairs(newHead -> next)”可以使“head -> next”指向链表的第三个节点。

我期望“swapPairs(newHead -> next)”会返回一个链表指针，其中链表4 -> 3 -> 5”指向“head -> next”。

我认为它会返回包含值4的节点，并且所有对节点在链表的第二个节点之后都被交换。

Answer 1

代码将按预期工作。

以单链表 1->2-3->4->5 为例：

在函数

swapPairs()

中，对于每对节点，考虑

head

是指向旧头节点的指针，而

newHead

将成为指向交换对的新头节点的指针。

为每个相邻的节点对调用

swapPairs()

，此函数返回交换对的第一个节点，该节点将被指定为指向旧头节点的

next

指针。 (

head->next

)

第一次调用函数 swapPairs() 时，

head

将指向 1，

newHead

指向 2。

第二次（递归）调用 swapPairs() 时，

head

将指向 3，

newHead

指向 4。

在第三次调用（递归）时，

head

将指向 5，并且

head->next

为 NULL。

head

为 NULL 或

head->next

为 NULL 是导致递归按照此代码停止的基本情况：

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

当第三次调用将旧头（5）返回给其调用者时，在调用者中，调用者中交换对的旧头节点的

head->next

现在将设置为5。这导致节点3现在指向5：

根据代码，

newHead

4 将被设置为指向旧的头节点 (3)：

newHead -> next = head; 
    return newHead; 

因此 4 将返回到之前的

swapPairs()

调用。因此，当返回给调用者时，4 和 3 会被交换。 （即第一次递归调用）。

现在在执行的第一个调用中，旧的头（1）将被设置为指向返回的4。剩下的就是让

newHead

现在指向 2，并将 2 返回给

main()

或在整个链表上调用 swapPairs 的调用者。