[LintCode/LeetCode] Rotate List

Blackjun 發(fā)布于2019-08-14 15:22 / 3595人閱讀

摘要：而后吾當依除取余之法，化大為小，則指針不致于越界也。后欲尋右起第結(jié)點，令快指針先行數(shù)日，及至兩指針相距為，便吟鞭東指，與慢指針策馬共進。快慢指針亦止于其所焉。舞動長劍，中宮直入，直取首級，而一掌劈空，已鴻飛冥冥。自此，一代天驕，霸業(yè)已成。

Problem

Given a list, rotate the list to the right by k places, where k is non-negative.

Example

Given 1->2->3->4->5 and k = 2, return 4->5->1->2->3.

Note

這是一道有故事的題目。
k有多大？其翼若垂天之云，則或長于鏈表。鏈表幾長？北海也，天池也，其廣數(shù)千里，則k亦可容于鏈表也。
故吾必先窮盡鏈表之長度，如若head為null，抑或其長可為k所整除，則此題不必再做，返回head可也。
而后吾當依除len取余之法，化大k為小k，則指針不致于越界也。后欲尋右起第k結(jié)點，令快指針先行數(shù)日，及至兩指針相距為k，便吟鞭東指，與慢指針策馬共進。則快指針行至null時，慢指針可至右起第k處矣。
方是時也，孤燈長夜，指飛鍵落。如風吹敗葉，雨打窗欞。快慢指針亦止于其所焉。此時看官不妨溫酒一盞，看那鏈表翻轉(zhuǎn)，指針易位。那新頭目喚作curhead，正是slow所指之人。fast舞動長劍，中宮直入，直取head首級，而slow一掌劈空，null已鴻飛冥冥。
自此，curhead一代天驕，霸業(yè)已成。

Solution

public class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        ListNode fast = head, slow = head;
        int len = 0;
        while (fast != null) {
            fast = fast.next;
            len++;
        }
        if (head == null || k % len == 0) return head;
        fast = head;
        k = k % len;
        while (k-- > 0) fast = fast.next;
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        ListNode curhead = slow.next;
        slow.next = null;
        fast.next = head;
        return curhead;
    }
}