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.
思路：每次交换cur1和cur2，使用dummy保证了pre的初始赋值的正确性，同时，注意next有可能为空。
/** * 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 NULL; ListNode dummy(-1); dummy.next = head; ListNode* pre = &dummy; ListNode* cur1 = head; ListNode* cur2 = head->next; ListNode* next = NULL; // swap cur1 and cur2 while(cur1 && cur2) { next = cur2->next; pre->next = cur2; cur2->next = cur1; cur1->next = next; pre = cur1; cur1 = next; // next may be NULL if(next == NULL) break; else cur2 = next->next; } return dummy.next; } };
[LeetCode] Swap Nodes in Pairs
原文：http://www.cnblogs.com/diegodu/p/4279749.html