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; //自己畫圖兴枯，設(shè)定各個(gè)指針爽茴，然后找出它們之間的關(guān)系窒篱，關(guān)鍵是鏈表不能斷
ListNode* pnext = ptr2->next; //自己畫圖崭篡，設(shè)定各個(gè)指針，然后找出它們之間的關(guān)系掘而，關(guān)鍵是鏈表不能斷
ptr2->next = nextstart;
pnext->next = ptr2;
ptr1->next = pnext;
ptr1 = ptr2;
ptr2 = nextstart;
}
return fakehead->next;
}
};
