提问人:Yang Ernie Chen 提问时间:10/15/2023 最后编辑:Weather VaneYang Ernie Chen 更新时间:10/15/2023 访问量:47
LeetCode 24 - 成对交换节点(代码的解释和可视化)
LeetCode 24 - Swap Nodes in Pairs (Explanation and Visualization of the code)
问:
/**
* 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 的节点,并且在链表的第二个节点之后交换所有对节点。
答:
代码将按预期工作。
以单链表 1->2->3->4->5 为例,函数中处理的最终结果将使列表为 2->1->4->3->5。swapPairs()
在函数内部,对于每对节点,认为它是指向旧头节点(即该对中的第一个节点)的指针,并将成为指向要交换的对的新头节点(即该对中的第二个节点)的指针。swapPairs()
head
newHead
swapPairs()
为整个列表中的每一对相邻节点调用,此函数返回交换对的第一个节点,该节点需要分配为指向前一对尚未交换的旧头节点的指针。next
演练:
对于函数的第一次调用,将指向 1 并指向 2。swapPairs()
head
newHead
在第二次调用(递归)时,将指向 3 并指向 4。swapPairs()
head
newHead
在第三次调用(递归)时,将指向 5 并且为 NULL。 NULL 或 NULL 是导致递归停止的基本情况,如以下代码所示:head
head->next
head
head->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(如 所指出的)将返回到上一个调用。newHead
swapPairs()
现在,当我们回到 的第一个调用时:旧的头(指向 1)将被设置为指向 4,该 4 是从 while 的第一个递归调用返回为对 (3,4) 的第一个节点指向 2。剩下的就是现在指向 1,因此 1 和 2 的交换现在已经完成,然后将指针(指向 2)返回给在整个链表上调用的任何其他调用方。swapPairs()
swapPairs()
newHead
newHead->next
newHead
main()
swapPairs()
评论