lintcode-170-回転チェーンテーブル

170-回転チェーンテーブル
チェーンテーブルが与えられ、チェーンテーブルが回転し、各ノードがk個の位置を右に移動するようにし、kは非負の数である
サンプル
チェーンテーブル1−>2−>3−>4−>5−>nullおよびk=2は、4−>5−>1−>2−>3−>nullを返す
タブ
基本実装チェーンテーブル
構想
lintcode-166-チェーンテーブルの最後からn番目のノードの考え方を利用して、回転チェーンテーブルはこのチェーンテーブルの最後からk番目のノードをヘッダノードとして、チェーンテーブルを再接続します.ただし、kの値はチェーンテーブルの長さより大きい場合があるので、まずチェーンテーブルの長さlenを求め、k%lenをkの値に設定します.
code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    /**
     * @param head: the list
     * @param k: rotate to the right k places
     * @return: the list after rotation
     */
    ListNode *rotateRight(ListNode *head, int k) {
        // write your code here
        if (k <= 0 || head == NULL) {
            return head;
        }
        
        int len = 0;
        ListNode *temp = head;
        while (temp != NULL) {
            temp = temp->next;
            len++;
        }
        ListNode *p1 = head, *p2 = head, *p3 = head;
        k = k % len;
        if (k == 0) {
            return head;
        }
        for (int i = 0; i < k; i++) {
            p1 = p1->next;
        }
        while (p1->next != NULL) {
            p1 = p1->next;
            p2 = p2->next;
            p3 = p3->next;
        }
        p2 = p2->next;
        p3->next = NULL;
        p1->next = head;
        return p2;
    }
};

転載先:https://www.cnblogs.com/libaoquan/p/7277112.html