写在前面
今天做一道关于链表交换节点的题(24. 两两交换链表中的节点 - 力扣（LeetCode）), 发现在力扣的调试环境中输出节点比较麻烦, 而且不是会员的话判题速度其实很慢, 那么就试试在本地环境中配置一套专为链表类型题打造的调试环境吧~
基本头文件
#include <iostream>
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* next1) : val(x), next(next1) {}
};
主要就是链表节点的结构体了, 这里我为避免类成员与外部参数重名, 倒数第二行的next我设置为next1, 这个影响不大.
链表的输出(打印)
这里给出我写的链表输出的操作符重载版本:
ostream& operator<<(ostream& os, ListNode* lp) {
ListNode* cur = lp;
while (cur != nullptr) {
os << cur->val << " -> ";
cur = cur->next;
}
os << "∅";
return os << endl;
}
这里的逻辑也比较简单, 就是遍历然后next向后移动, 需要注意的有两点:
- 最后的
endl, 在cppprimer中提到最好不要在操作符重载中加上endl, 这里是为了方便.. - 最好不要对原始节点进行操作, 而是应该重新给出一个节点指针
cur, 要不然会出现一些意想不到的问题.
链表结点的数据准备
这里就是测试用例部分了, 对于一个链表, 当然不能像数组那样方便地给出, 这里跟遍历节点一样, 仍是通过循环给出链表的实现:
int main(int argc, char* argv[]) {
ListNode* head = new ListNode(1);
ListNode* cur = head;
for (auto& i : {2, 3, 4}) {
cur->next = new ListNode(i);
cur = cur->next;
}
cout << head;
// 这里就是题目中函数的调用了, 下面是一个示例(24题)
/*
Solution s;
cout << s.swapPairs(head);
*/
// 别忘了释放内存(虽然系统会帮我们释放)
delete head;
return 0;
}
这里的输出显示为:
1 -> 2 -> 3 -> 4 -> ∅
看起来还不错吧~
最后给出24题的代码:
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if (!head || !head->next) return head;
using Lp = ListNode*;
Lp cur = head;
head = head->next;
cur->next = head->next;
head->next = cur;
Lp pre = cur;
cur = cur->next;
while (cur && nullptr != cur->next) {
pre->next = cur->next;
cur->next = cur->next->next;
pre->next->next = cur;
// update
pre = cur;
cur = cur->next;
}
return head;
}
};
运行结果为:
2 -> 1 -> 4 -> 3 -> ∅