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

川长思鸟来 2022-09-08 14:53 117阅读 0赞

## 前言 ##

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

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

本文档详细代码见：[git仓库][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

[24.]: https://leetcode-cn.com/problems/swap-nodes-in-pairs/
[-]: https://leetcode-cn.com/problems/swap-nodes-in-pairs/solution/liang-liang-jiao-huan-lian-biao-zhong-de-jie-di-91/
[git]: https://github.com/da1234cao/data_structure/tree/master/leetcode