题目描述
给定一个链表,两两交换其中相邻的结点,并返回交换后的链表。
你不能只是单纯的改变结点内部的值,而是需要实际的进行结点交换。
样例
给定 1->2->3->4, 你应该返回链表 2->1->4->3。
算法
(模拟) $O(L)$
- 添加虚拟头结点
dummy
。 - 定义
cur
指针初始指向dummy
。 - 定义
first
为cur->next
,second
为first->next
;若first
或second
为空,则终止循环。 - 按照一定的次序,修改
cur
、first
和second
结点的next
指针,具体参见代码。 - 将
cur
指向修改后的first
,接着从第 3 步循环。
时间复杂度
- 仅遍历一遍所有结点,所以是 $O(L)$。
空间复杂度
- 仅使用常数的额外空间。
C++ 代码
/**
* Definition for singly-linked list.
* 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) {
ListNode* dummy = new ListNode(0, head);
ListNode* cur = dummy;
while (cur != NULL) {
ListNode* first = cur -> next;
if (first == NULL)
break;
ListNode* second = first -> next;
if (second == NULL)
break;
cur -> next = second;
first -> next = second -> next;
second -> next = first;
cur = first;
}
return dummy -> next;
}
};
请问这里的ListNode* dummy = new ListNode(0, head);,0是不是虚拟头节点的val啊,随便什么值都可以吗?
对,随便都可以
wzc聚聚,ListNode* dummy = new ListNode(0, head);是不是指建立一个值为0的指向head的节点?
是滴