leetcode: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つの下付きラベルは、下付きラベル間のチェーンテーブルの順序を反転させ、他の部分は変わらない.
チェーンテーブルを反転する操作は3つのポインタで維持され、最後のポインタが空のポインタである可能性があることに注意してください.
反転開始位置と終了位置のnextリンクを考慮すると、反転開始位置の前のポインタをフロントポインタbeginで格納すると操作が容易で、チェーンテーブルが最初から反転している場合、headポインタが変化します.

/**
 * 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) {
        ListNode *begin,*p1,*p2,*p3;
        int i;
        begin=head;
        for(i=1;inext;
        if(m!=1)p1=begin->next;
        else p1=begin;
        p2=p1->next;
        if(p2)p3=p2->next;
        for(i=0;inext=p1;
            p1=p2;
            p2=p3;
            if(p2)p3=p2->next;
        }
        if(m!=1) {
            begin->next->next=p2;
            begin->next=p1;
        }
        else {
            begin->next=p2;
            head=p1;
        }
        return head;
    }
};
// blog.csdn.net/havenoidea 

問題解決ディレクトリ