1、

Reverse Linked List II 

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m =
2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

分析：開始看题目以为是仅仅交换两个指定位置的值。后来写出代码来出错。才发现是翻转位置m和n直接的链表，我的基本思路是先用双指针法找到要翻转链表的位置，将链表分成三段，要翻转的前一段，中间呀翻转的段，和剩下的段。最后写出代码来特别繁琐。例如以下所看到的：

class Solution {

public:

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

        if(m < 1 || m >= n){

            return head;

        }

        //双指针法找到要翻转的链表段

        ListNode* node1 = head;

        ListNode* node2 = head;

        int dis = n - m;

        int i = 0;

        for(; i<dis && node2; ++i){

            node2 = node2->next;

        }

        if(i<dis){

            return head;

        }

        while(i<n-2 && node2){

            node1 = node1->next;

            node2 = node2->next;

            ++i;

        }

        //node3为要翻转的链表段的開始结点

        ListNode* node3 = node1->next;

        if(m == 1){

            node1 = NULL;

            node3 = head;

        }else{

            node1->next = NULL;

            node2 = node2->next;

            if(!node2){

                return head;

            }

            ++i;

        }

        //node4为剩下的链表

        ListNode* node4 = NULL;

        node4 = node2->next;

        node2->next = NULL;

        //假设链表长度大于n时。能够进行

        if(i == n-1){

            ListNode* newHead = reverseList(node3); //翻转中间链表

            //连接三段链表

            node3->next = node4;

            if(m !=1 ){

                node1->next = newHead;

                return head;

            }else{

                return newHead;

            }

        }

        return head;

    }

    ListNode* reverseList(ListNode* head){

        ListNode* node1 = NULL;

        ListNode* node2 = head;

        ListNode* tempNode = NULL;

        while(node2){

            tempNode = node2->next;

            node2->next = node1;

            node1 = node2;

            node2 = tempNode;

        }

        return node1;

    }

};

改进：上述代码非常繁琐。搜了别人的代码，非常简洁，问题在于上述对中间链表进行了两次遍历，缩短为一次遍历。可缩减代码。上列代码没有考虑异常情况，比方链表长度<m或者<n等情况。

class Solution {

public:

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

        // Start typing your C/C++ solution below

        // DO NOT write int main() function

        if (head == NULL)

            return NULL;

        ListNode *q = NULL;

        ListNode *p = head;

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

        {

            q = p;

            p = p->next;

        }

        ListNode *end = p;

        ListNode *pPre = p;

        p = p->next;

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

        {

            ListNode *pNext = p->next;

            p->next = pPre;

            pPre = p;

            p = pNext;

        }

        end->next = p;

        if (q)

            q->next = pPre;

        else

            head = pPre;

        return head;

    }

};