Swap Nodes in Pairs
Given a linked list, swap every two adjacent nodes and return its head.
For example,
Given1->2->3->4, you should return the list as2->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.
相邻两个节点为一组，交换一组内节点的位置，如1和2交换，3和4交换。
不能改变节点里values的值，而且只能使用常量的空间。
解题思路：
- 设置一个dummy头节点方便对第一个节点进行操作。
- 然后有三个指针 pre，first，second。 first和second分别指向待交换的第一个和第二个节点，pre指针指向first之前的那个节点。
- 交换first和second指针的节点，交换过程如图：
- 交换后，判断first节点后面有没有节点了，有一个还是有两个节点。
- 如果后面有一个节点或者没有节点，链表交换完毕，退出循环。
- 如果后面有两个节点，first后移，设置pre和second的新位置，再次执行上面的交换操作。
- 循环退出后，链表已经交换了顺序了。
- 删除dummy节点，返回head指针。
代码如下：
class Solution {
public:
ListNode *swapPairs(ListNode *head) {
if(head == NULL)
return NULL;
ListNode *dummy = new ListNode();
dummy->next = head;
ListNode *pre = dummy,*first = head,*second = head->next;
if(second == NULL){
//只有一个节点
delete dummy;
return head;
}
else{
//先交换第一个和第二个节点
pre->next = second;
first->next = second->next;
second->next = first;
}
while(true){
if(first->next == NULL || first->next->next == NULL)
//first后面没有节点或者只有一个节点
break;
else{
//有两个节点
pre = first;
first = first->next;
second = first->next;
pre->next = second;
first->next = second->next;
second->next = first;
}
}
head = dummy->next;
delete dummy;
return head;
}
};