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.
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if(head==NULL||head->next==NULL)
return head;
ListNode* fakehead = new ListNode(-1);
fakehead->next = head; //牢记这种方法
ListNode* ptr1 = fakehead;
ListNode* ptr2 = head;
while(ptr2!=NULL&&ptr2->next!=NULL)
{
ListNode* nextstart = ptr2->next->next; //自己画图，设定各个指针，然后找出它们之间的关系，关键是链表不能断
ListNode* pnext = ptr2->next; //自己画图，设定各个指针，然后找出它们之间的关系，关键是链表不能断
ptr2->next = nextstart;
pnext->next = ptr2;
ptr1->next = pnext;
ptr1 = ptr2;
ptr2 = nextstart;
}
return fakehead->next;
}
};
