<p style="box-sizing: border-box; margin-top: 0px; margin-bottom: 10px; color: rgb(51, 51, 51); font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14.399999618530273px; line-height: 30px;">Given a linked list, swap every two adjacent nodes and return its head.</p><p style="box-sizing: border-box; margin-top: 0px; margin-bottom: 10px; color: rgb(51, 51, 51); font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14.399999618530273px; line-height: 30px;">For example,<br style="box-sizing: border-box;" />Given <code style="box-sizing: border-box; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 12.800000190734863px; padding: 2px 4px; color: rgb(199, 37, 78); background-color: rgb(249, 242, 244); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px;">1->2->3->4</code>, you should return the list as <code style="box-sizing: border-box; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 12.800000190734863px; padding: 2px 4px; color: rgb(199, 37, 78); background-color: rgb(249, 242, 244); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px;">2->1->4->3</code>.</p><p style="box-sizing: border-box; margin-top: 0px; margin-bottom: 10px; color: rgb(51, 51, 51); font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14.399999618530273px; line-height: 30px;">Your algorithm should use only constant space. You may <span style="box-sizing: border-box; font-weight: 700;">not</span> modify the values in the list, only nodes itself can be changed.</p>
/** * 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) return head; ListNode *dummy = new ListNode(-1); dummy->next = head; ListNode *p1 = head; ListNode *p2 = p1->next; ListNode *prev = dummy; while(p1 && p2) { prev->next = p2; p1->next = p2->next; p2->next = p1; prev = p1; p1 = p1->next; if(p1) p2 = p1->next; else break; } return dummy->next; } };