Given a linked list, swap every two adjacent nodes and return its head.
You may not modify the values in the list’s nodes, only nodes itself may be changed.
Example:
Given1->2->3->4
, you should return the list as2->1->4->3
.
交换链表的每两个相邻节点。样例不保证是偶数个节点,也可能出现奇数个节点,此时最后一个节点就不要交换了。 交换过程中需要使用3个指针,当前指针ln1,当前指针的下一个指针ln2以及ln1的副本ln3用于更改ln1的next。具体怎么变换的,在纸上画一画就知道了,下面是完整代码。
class Solution {
public:
ListNode* swapPairs(ListNode* head)
{
if (head == NULL || head->next == NULL)
return head;
ListNode *ln1 = head, *ln2 = ln1->next, *ln3 = ln1, *new_head = ln2;
bool first = true;
while (ln1) {
ln2 = ln1->next;
if (ln2 == NULL)
break;
ln1->next = ln2->next;
ln2->next = ln1;
if (!first) { // 第一次不需要更改ln3的指向
ln3->next = ln2;
}
first = false;
ln3 = ln1;
ln1 = ln1->next;
}
return new_head;
}
};
本代码提交AC,用时4MS,只击败了1.83%,郁闷,我这已经是O(n)的时间复杂度,O(1)的空间复杂度,不知道还可以怎样优化。
更漂亮的递归版本:
class Solution {
public:
ListNode* swapPairs(ListNode* head)
{
if (head == NULL || head->next == NULL)
return head;
ListNode* second = head->next;
head->next = swapPairs(head->next->next);
second->next = head;
return second;
}
};
本代码提交AC,用时6MS,无语了。