LeetCode 24 - 成对交换节点(代码的解释和可视化)

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

提问人:Yang Ernie Chen 提问时间:10/15/2023 最后编辑:Weather VaneYang Ernie Chen 更新时间:10/15/2023 访问量:47

问:

/** 
 * 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 -> 接下来是指向包含值 3(第 3 个节点)的节点的指针。

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

我预计“swapPairs(newHead -> next)”将返回一个链表指针,链表 4 -> 3 -> 5“ 到”head -> next”。

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

c 递归 数据结构 链接列表 交换

评论

0赞 n. m. could be an AI 10/15/2023
请正确格式化您的问题。将代码块缩进 4 个字符。
2赞 Fe2O3 10/15/2023
最好的解释是你在一张纸上画出操作,然后向你的橡皮鸭解释:meta.stackoverflow.com/a/281271/17592432
1赞 n. m. could be an AI 10/15/2023
但是为什么“head -> next = swapPairs(newHead -> next)”返回包含值 3 的节点你怎么知道?请发布您直接观察到的内容,而不是您推断的内容。一个最小的可重复的例子将是传达这些信息的最佳方式。

答:

0赞 storsan 11/29/2023 #1

代码将按预期工作。

以单链表 1->2->3->4->5 为例,函数中处理的最终结果将使列表为 2->1->4->3->5。swapPairs()

在函数内部,对于每对节点,认为它是指向旧头节点(即该对中的第一个节点)的指针,并将成为指向要交换的对的新头节点(即该对中的第二个节点)的指针。swapPairs()headnewHead

swapPairs()为整个列表中的每一对相邻节点调用,此函数返回交换对的第一个节点,该节点需要分配为指向前一对尚未交换的旧头节点的指针。next

演练:

对于函数的第一次调用,将指向 1 并指向 2。swapPairs()headnewHead

在第二次调用(递归)时,将指向 3 并指向 4。swapPairs()headnewHead

在第三次调用(递归)时,将指向 5 并且为 NULL。 NULL 或 NULL 是导致递归停止的基本情况,如以下代码所示:headhead->nextheadhead->next

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

当第三次调用将旧头 (5) 返回给其调用方时,调用方中待交换对(3 和 4)的旧头节点的调用方现在将设置为 5。这会导致节点 3 现在指向 5:head->next

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

newHead根据代码,指向 4 将设置为指向旧的头节点 (3):

newHead -> next = head; 
    return newHead; 

节点 3 和 4 的交换已完成。而 4(如 所指出的)将返回到上一个调用。newHeadswapPairs()

现在,当我们回到 的第一个调用时:旧的头(指向 1)将被设置为指向 4,该 4 是从 while 的第一个递归调用返回为对 (3,4) 的第一个节点指向 2。剩下的就是现在指向 1,因此 1 和 2 的交换现在已经完成,然后将指针(指向 2)返回给在整个链表上调用的任何其他调用方。swapPairs()swapPairs()newHeadnewHead->nextnewHeadmain()swapPairs()