[LeetCode問題解]:Reverse Nodes in K-Groups

4071 ワード
LeetCode
前言
 
【LeetCode問題解】シリーズ転送ゲート:http://www.cnblogs.com/double-win/category/573499.html
 
1.タイトルの説明
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.
For example, Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5
2.題意
チェーンテーブルを指定し、チェーンテーブルをk要素のグループに順番に分け、各グループの要素を逆置きします.
注意:グループ内の要素がk個未満の場合、逆転操作は行われません.
3.考え方
挿入法によりチェーンテーブルを逆置きし,再帰法を用いることができる.
(1)チェーンテーブルを逆さにして、文章を参考にすることができます.
(2)チェーンテーブルをk要素グループに分ける.
挿入点を指すポインタpreを設定します.
挿入した要素がk個を満たすと再帰する.
例えば、チェーンテーブルは1->2->3->4->5 k=2
グループを1->2 3->4に分けることができます.
for i range from 1 to k
tmp <- head
#tmpをpreに挿入した後
head = head->next
(3)再帰
上記の手順が完了すると、head->val=3となり、次の処理に進む
(4)終了条件は,残りのグループの要素がk個未満であり,そのグループを直接戻し,逆転しない.
4:解法
class Solution {

public:

    int getListLen(ListNode *head){

        int len=0;

        ListNode *tmp=head;

        while(tmp){len++;tmp=tmp->next;}

        return len;

    }

    ListNode *reverseKGroup(ListNode *head, int k) {

       if(k<=1|| !head || !head->next) return head;

        int len=getListLen(head);

        if(len<k) return head;



        ListNode *pre=new ListNode(0);

        ListNode *change=head;



        for(int j=1;j<=k;j++){

                ListNode *tmp = change;

                change = change->next;

                tmp->next = pre->next;

                pre->next=tmp;

        }

        head->next=reverseKGroup(change,k);

        return pre->next;

    }

};


作者:Double_Win出典:http://www.cnblogs.com/double-win/p/3896010.html声明:本人のレベルが限られているため、文章の表現とコードの面で不適切な点があれば、批判を歓迎します.
Enable nested virtualization in VirtualBox
453.ツリーをチェーンテーブルに分解する