24. 两两交换链表中的节点

LeetCode题目:C++递归

给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。

示例 1:

输入:head = [1,2,3,4]
输出:[2,1,4,3]

示例 2:

输入:head = []
输出:[]

示例 3:

输入:head = [1]
输出:[1]

提示:

  • 链表中节点的数目在范围 [0, 100] 内
  • 0 <= Node.val <= 100

初始代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        
    }
};

解决思路

递归实现

先观察题目。发现“两两交换”这个操作对于一个有n个元素(n>1)的链表来说,是重复操作–即可以使用递归处理的。

类比于斐波那契数列,我们先看看n≤1的情况,发现函数返回值就是head。那么可以写出:

 ListNode* swapPairs(ListNode* head) {
        if(head==NULL||head->next==NULL) //n=0或n=1
            return head;
    }

然后在看看n≥2的情况。链表中的第二个节点与第一个节点交换后,第二个节点变成了新的头节点;原本的头节点变成了第二个节点,并且连接着链表后续的内容。

根据递归的相关知识(把递归过程看作一个栈),假设现在链表为[1,2,3,4]。那么我们可以得到代码:

  • ListNode* tmp =head->next;
    • 链表中的每两个节点,取第一个节点为head,第二个节点为tmp。
    • 如果链表中元素个数为奇数,tmp=NULL。
  • head->next=swapPairs(tmp->next);
    • 每次递归的过程都被存入了栈中,直到传入的节点为空或传入节点的下一个节点为空。
    • 因为是每两个节点取一次head和tmp,所以当tmp=NULL(链表中元素个数为奇数),或tmp->next=NULL(tmp是链表最后一个元素)时,停止递归的“递”操作。
    • “归”操作就是把栈顶元素弹出,把它的值传给新的栈顶元素。
    • 该操作就是将head的next指针指向tmp的下一个节点。
  • tmp->next=head;
    • 该操作将tmp的next指针指向head节点。
  • return tmp;
    • 最后的tmp便是新的head节点。

把tmp->next=…理解为“将tmp节点的next指针指向某个节点”,而不是“tmp节点的next指针等于某个节点”就很好明白了,以下是流程图和完整代码

流程图

完整代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(head==NULL||head->next==NULL)
            return head;
        ListNode* tmp=head->next;
        head->next=swapPairs(tmp->next);
        tmp->next=head;
        return tmp;
    }
};
Subscribe
提醒
0 评论
Inline Feedbacks
View all comments
0
在此留下你的评论x