Given a linked list, swap every two adjacent nodes and return its head.
For example,
Given 1->2->3->4
, you should return the list as 2->1->4->3
.
Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.
分析
算法一:
看到题目,首先想到使用双指针,来进行交换,但是交换过后,会存在一个连接断开的问题:
a->b->c->d->e...
交换c,d以后的结果是 a->b d->c->e
|_____|
所以需要三个指针,将交换以后的连接更新一下。
边界条件:
1 开始的两个node,并不需要更新连接
2 node总数可能是奇数,可能是偶数,所以判定的时候需要注意发生 a == NULL 并调用 a->next这种 runtime error的情况
使用三个指针,两个指向节点,一个指向某个节点中的next,所以应该是ListNode **,用来连接交换后的新的链路
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if(head == NULL) return NULL;
ListNode **pp = & head, *a, *b;
while((a = *pp) && (b = a->next)){
a->next = b->next;
b->next = a;
*pp = b;
pp = &(a->next);
}
return head;
}
};
算法二:
使用递归算法,使用两个指针指向当前节点和下一个,并对剩下的 list 使用swapPairs
/**
* 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) {
if(head == NULL || head->next == NULL) return head;
ListNode * a = head, *b = head->next,*tmp;
tmp = b->next;
b->next = a;
a->next = swapPairs(tmp);
return b;
}
};