两两交换链表中的节点

递归解法

大佬解释递归

代码语言：javascript复制

class Solution {
public:
    ListNode* swapPairs(ListNode* head) 
    {
        //在递归到最后两个节点的时候，返回head==NULL,相当于把倒数第二个节点next赋值为NULL
        //就是把倒数第一个节点和倒数第二个节点进行交换
        if (head == NULL || head->next == NULL)
        {
            return head;
        }
        //函数返回的是要交换两个节点的后面一个节点，相当于将交换后的两个节点在放入原链表中
        ListNode* newlist = swapPairs(head->next->next);
        //下面是进行两个节点交换的代码
        ListNode* p = head->next;
        //把原先后一个节点next指向它的前一个节点
        p->next = head;
        //前一个节点head指向的节点，接收newlsit的值
        head->next = newlist;//原先p节点在head节点之后，此时head与p的位置互换了
        //返回p节点，因为此时p排在head前面，原先指向head的节点，此时应该指向p
        return p;
    }
};

非递归解法

代码语言：javascript复制

class Solution {
public:
    ListNode* swapPairs(ListNode* head) 
    {
        ListNode* dummyNode = new ListNode(0);
          dummyNode->next= head;//虚节点（指向第一个有数据节点的头结点）
        ListNode* temp = dummyNode;//用来遍历链表
        while (temp->next != NULL && temp->next->next != NULL)//当还剩一个或没有节点的时候，停止交换
        {
            //每一次将temp后面两个节点进行交换操作
            ListNode* node1 = temp->next;
            ListNode* node2 = temp->next->next;
            //交换
            node1->next = node2->next;
            node2->next = node1;
            temp->next = node2;
            //更新temp位置
            temp = node1;
        }
        return dummyNode->next;
    }
};

递归

0 人点赞