代码随想录算法训练营第四天-链表-24. 两两交换链表中结点

• 重点是使用虚拟头结点，这样如果整个链表是个空链表，处理起来也会保持代码一致
• 内部处理过程是一个复杂过程
  • 要定义一个当前结点，要通过这个当前结点cur，把其后要交换的两个结点获取到
  • 通过当前结点，定义两个变量，node_1st，和node_next_1st
    • node_1st = cur->next;表示要交换的第一个结点
    • node_next_1st = cur->next->next->next;表示在交换区域外的准备交换的第一个结点
    • 交换区域外是指准备交换两个结点之外的，准备下一次交换两个结点所在区域
  • 交换过程：
    • cur->next = cur->next->next;让当前结点指向交换区域的第二个结点，也就是与第一个结点断开链接
    • cur->next->next = node_1st;让原第二个结点指向原第一个结点（链接反转）
    • node_1st->next = node_next让原第一个结点指向交换区域外的第一个结点，这个代码相比于老师提供的做了优化，要检测是否正确
    • cur = node_1st;让当前结点移动到已经交换位置后的第二个结点上，也就是让其移动到准备下一次交换的两个结点前的一个结点上
• 上面的过程不看混是不可能的吧，可以参照网站的图片和B站上的视频来加深理解吧

#include <iostream>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(): val(0), next(nullptr) {}
    ListNode(int v): val(v), next(nullptr) {}
    ListNode(int v, ListNode* node): val(v), next(node) {}
};

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* visualHead = new ListNode(0);
        visualHead->next = head;
        for(ListNode* cur = visualHead, *node_1st, *node_next_1st; cur->next != nullptr && cur->next->next != nullptr; cur = node_1st) {
            node_1st = cur->next;
            node_next_1st = cur->next->next->next;

            cur->next = cur->next->next;
            cur->next->next = node_1st;
            node_1st->next = node_next_1st;
        }
        ListNode* ret_head = visualHead->next;
        delete visualHead;
        return ret_head;
    }
    void show(ListNode* head) {
        for (auto* p = head; p != nullptr; p = p->next)
            std::cout << p->val << " ";
        std::cout << std::endl;
    }
};
int main()
{
    ListNode* head = nullptr;
    for (int val; std::cin >> val; head = new ListNode(val, head));
    Solution s;
    head = s.swapPairs(head);
    s.show(head);
    return 0;
}

• 测试数据：录入数据5 4 3 2 1 a，会生成1->2->3->4->5这样一个链表，字母a表示数据录入结束
• 汇总