当前位置：首页 > news >正文

OJ 两两交换链表中的节点

news 2025/5/11 5:23:20

题目：

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

示例：

代码分析：

class Solution {
public:ListNode*_swap(ListNode*cur){//判断当前节点是否是空的（cur一开始是接收头节点，同时后面还会接收未节点），//如果是空的则直接返回if(cur==nullptr) return nullptr;//如果该节点的下一个是空，那么没有交换的必要if(cur->next==nullptr) return cur;//设置当前节点的后一个节点的后一个节点，这样方便指针的指向和之后的递归操作ListNode*_next=cur->next->next;//记录当前节点的下一个节点ListNode* second = cur->next;//进行节点指向的改变，将当前节点的后一个节点的后一个节点的 next指针指向当前节点cur->next->next =cur;//也就是让当前节点的 下一个节点 的next指针指向当前节点//利用递归操作进行递归当前节点的下一个节点cur->next = _swap(_next);最后返回return second;}ListNode* swapPairs(ListNode* head) {return _swap(head);}
};

根据示意图可以得出，链表上的节点是前后节点进行交换的，所以需要该动前后节点的指针指向，这里使用递归的方式进行改动。
swap(ListNode* cur)：
这是一个递归函数，用于递归地处理链表，直到链表结束（即遇到 nullptr 或只有一个节点时）。
函数的参数 cur 是当前正在处理的节点。
如果 cur 是 nullptr 或 cur->next 是 nullptr（即链表为空或只有一个节点），则函数直接返回 cur，因为没有节点对可以反转。
否则，函数首先保存 cur->next->next（即当前节点的下一个节点的下一个节点，记作 _next）以便后续递归调用。
然后，它执行“翻转”操作：将 cur->next 的 next 指针指向 cur，从而实现了一对节点的逻辑反转。
接着，它递归地调用自身来处理剩余的链表（从 _next 开始）。
最后，函数返回 cur->next，即新链表的头节点（因为 cur 和 cur->next 已经交换了位置）。
swapPairs(ListNode* head)：
这是对外的接口函数，用于启动反转每对节点的过程。
它简单地调用了 _swap(head) 并返回结果。