[数据结构与算法]leetcode 24 两两交换链表中的节点

前言

题目：24. 两两交换链表中的节点

参考答案：两两交换链表中的节点-力扣官方题解

本文档详细代码见：git仓库

提交代码

最开始，我的解题思路是，两个为一组互换。互换之后，后面的元素交换不影响前面已经交换过的元素，顺序遍历处理就好。然后，开始码思路，提交，然后报错。

编程，代价最大的错误是思路有问题。我用报错的测试用例，调试了下代码，发现，但后一组进行交换的时候，前一组已经交互的指针需要修正(即，后一组对前一组有影响)。

找到问题就好。我们重新构思，将后一组对前一组的影响考虑进去，再次编程，调试，通过。

我是按照人类思维进行代码模拟。参考答案给出了最直接的规律，即将人类的思维进行总结形成规律。两者等价。下面代码，为模拟交换过程。

#include <iostream>
#include <vector>

using namespace std;

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==nullptr || head->next==nullptr) // 空链表，或链表只包含一个元素，直接返回
            return head;
        
        // 变量名含义：当前交换组的第一、第二元素；前一组的交换后的第二个元素，后一组交换前的第一个元素
        ListNode *groupOne=head, *groupTwo=nullptr; 
        ListNode *prevGroupTwo=nullptr, *nextGroupOne=nullptr;

        ListNode *result = head->next; // 如果节点个数大于等于2，第二个节点为新的头结点
        while(groupOne != nullptr){
            groupTwo = groupOne->next; 
            if(groupTwo != nullptr){
                nextGroupOne = groupTwo->next; // 站在下一个待两两交换的位置
                groupOne->next = nextGroupOne; // 链表交换节点
                groupTwo->next = groupOne; // 链表交换节点
                if(prevGroupTwo != nullptr)
                    prevGroupTwo->next = groupTwo; // 修正前一组的指针指向
                prevGroupTwo = groupOne; // 前往下一个位置.因为当前组的第一个位置，已经被交换到第二个位置(作为前一组的第二个位置)。
                groupOne = nextGroupOne; // 前往下一个位置
            }else{ // 待交换的第二个节点为空，此次两两交换只存在一个节点时，不动它
                break;
            }
        }

        return result; 
    }
};

int main(void){
    vector<int> tmpVec = {1,2,3};

    ListNode* head = nullptr; // 链表头节点,存储数据
    ListNode* it = head;
    if(tmpVec.size() >= 1){
        head = new ListNode();
        it = head;
        head->val = tmpVec[0]; // 单独给头结点赋值
        for(int i=1; i<tmpVec.size(); i++){
            ListNode* node = new ListNode(tmpVec[i]); // 在堆中申请空间
            it->next = node;
            it = it->next;
        }
    } 

    for(it=head; it!=nullptr; it=it->next)
        cout<<it->val<<" ";
    cout<<endl; 

    Solution s;
    head = s.swapPairs(head);

    for(it=head; it!=nullptr; it=it->next)
        cout<<it->val<<" ";
    cout<<endl;   

}

规律总结如下：

temp.next = node2
node1.next = node2.next
node2.next = node1