[LintCode/LeetCode] Rotate List

Blackjun 发布于2019-08-14 15:22 / 3562人阅读

摘要：而后吾当依除取余之法，化大为小，则指针不致于越界也。后欲寻右起第结点，令快指针先行数日，及至两指针相距为，便吟鞭东指，与慢指针策马共进。快慢指针亦止于其所焉。舞动长剑，中宫直入，直取首级，而一掌劈空，已鸿飞冥冥。自此，一代天骄，霸业已成。

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有多大？其翼若垂天之云，则或长于链表。链表几长？北海也，天池也，其广数千里，则k亦可容于链表也。
故吾必先穷尽链表之长度，如若head为null，抑或其长可为k所整除，则此题不必再做，返回head可也。
而后吾当依除len取余之法，化大k为小k，则指针不致于越界也。后欲寻右起第k结点，令快指针先行数日，及至两指针相距为k，便吟鞭东指，与慢指针策马共进。则快指针行至null时，慢指针可至右起第k处矣。
方是时也，孤灯长夜，指飞键落。如风吹败叶，雨打窗棂。快慢指针亦止于其所焉。此时看官不妨温酒一盏，看那链表翻转，指针易位。那新头目唤作curhead，正是slow所指之人。fast舞动长剑，中宫直入，直取head首级，而slow一掌劈空，null已鸿飞冥冥。
自此，curhead一代天骄，霸业已成。

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

云服务器 GPU云服务器 Rotate 旋转-rotate list 排序 list

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65689.html

[LintCode/LeetCode] Rotate Array

Problem Given an array, rotate the array to the right by k steps, where k is non-negative. Example Example 1: Input: [1,2,3,4,5,6,7] and k = 3Output: [5,6,7,1,2,3,4]Explanation:rotate 1 steps to the r...

chanthuang 2019-08-16 12:44 评论0 收藏0
[LintCode/LeetCode] Rotate Image

摘要：两种方法，转置镜像法和公式法。首先看转置镜像法原矩阵为转置后水平镜像翻转后所以，基本的思路是两次遍历，第一次转置，第二次水平镜像翻转变换列坐标。公式法是应用了一个翻转的公式如此翻转四次即可。二者均可，并无分别。 Problem You are given an n x n 2D matrix representing an image.Rotate the image by 90 de...

BenCHou 2019-08-14 15:22 评论0 收藏0
[LintCode/LeetCode] Meeting Rooms

Problem Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings. Example Given intervals = [[0,30],[...

Noodles 2019-08-16 12:34 评论0 收藏0
[LintCode/LeetCode] Nth to Last Node in List

摘要：依然是一道找倒数第个结点的链表题，用双指针做。先走，然后和一起走，直到为，的位置就是倒数第个位置。 Problem Find the nth to last element of a singly linked list. The minimum number of nodes in list is n. Example Given a List 3->2->1->5->null ...

Salamander 2019-08-14 15:22 评论0 收藏0
[LintCode/LeetCode] Copy List with Random Pointer

摘要：大体意思就是，先复制到，顺便将所有的放在再复制所有的到，顺便将所有的放在最后令，令，将和分离，返回的头结点 Problem A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. ...

Jacendfeng 2019-08-14 15:32 评论0 收藏0