题目描述
给定一个单向链表,依次交换每一对相邻的两个结点,返回修好后的链表头结点。
链表结点的数据结构:
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
样例
输入:1->2->3->4
输出:2->1->4->3
额外要求
- 不得修改链表中结点的
val
值,仅可以使用常数的空间。
算法
(模拟) $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(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummy = new ListNode(0);
dummy -> next = 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;
}
};