/**

  * Definition for singly-linked list.

  * struct ListNode {

  *     int val;

  *     ListNode *next;

  *     ListNode(int x) : val(x), next(NULL) {}

  * };

  */

 class Solution {

 public:

     ListNode* reverseBetween(ListNode* head, int m, int n)

     {

          if (!head || !head->next)

             return head;

         ListNode* dummy = new ListNode();

         dummy->next = head;

         ListNode* prev = dummy;

         for (int i = ; i < m - ; i++)

             prev = prev->next;

         ListNode* start = prev->next;

         ListNode* then = start->next;

         for (int i = ; i < n - m; i++)

         {

             start->next = then->next;

             then->next = prev->next;

             prev->next = then;

             then = start->next;

         }

         return dummy->next;

     }

 };

 class Solution {

 public:

     bool isPalindrome(ListNode* head)

     {

         if (!head || !head->next) return true;

         ListNode *slow = head, *fast = head;

         while (fast->next && fast->next->next) //找到中点

         {

             slow = slow->next;

             fast = fast->next->next;

         }

         ListNode *last = slow->next, *pre = head;

         while (last->next)  //反转

         {

             ListNode *tmp = last->next;

             last->next = tmp->next;

             tmp->next = slow->next;

             slow->next = tmp;

         }

         while (slow->next) //比较

         {

             slow = slow->next;

             if (pre->val != slow->val)

                 return false;

             pre = pre->next;

         }

         return true;

     }

 };

 /**

  * 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 || !head->next) return head;

         ListNode *t = head->next;

         head->next = swapPairs(head->next->next);

         t->next = head;

         return t;

     }

 };

 class Solution {

 public:

     ListNode* swapPairs(ListNode* head)

     {

         ListNode *dummy = new ListNode(-), *pre = dummy;

         dummy->next = head;

         while (pre->next && pre->next->next)

         {

             ListNode *t = pre->next->next;

             pre->next->next = t->next;

             t->next = pre->next;

             pre->next = t;

             pre = t->next;

         }

         return dummy->next;

     }

 };