leetcode -day30 Reverse Linked List II

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.
分析:タイトルを见始めて2つの指定位置の値だけを交换すると思って、それからコードを书いて间违いを出して、やっと反転位置mとnの直接のチェーンテーブルであることを発见して、私の基本的な考え方はまず双指针法でチェーンテーブルを反転する位置を探し当てて、チェーンテーブルを3段に分けて、反転する前の段、中间と反転する段、残りの段、最后にコードを书いてとても面倒です.次のようになります.

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(; inext;
        }
        if(inext;
            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;
    }
};

改善:上記のコードは煩雑で、他の人のコードを探して、とても簡潔で、問題は上記が中間チェーンテーブルに対して2回の遍歴を行って、1回の遍歴に短縮して、コードを縮小することができます.上の列のコードでは、チェーンテーブルの長さなどの異常は考慮されていません.

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;
    }
};