首页 > ACM题库 > LeetCode > LeetCode-Rotate List[链表]
2014
11-19

LeetCode-Rotate List[链表]

Rotate List

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

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

标签: Linked List Two Pointers
分析

先遍历一遍,得出链表长度$len$,注意$k$可能大于$len$,因此令$k \%= len$。将尾节点next指针指向首节点,形成一个环,接着往后跑$len-k$步,从这里断开,就是要求的结果了。

代码1

// LeetCode, Remove Rotate List
// 时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    ListNode *rotateRight(ListNode *head, int k) {
        if (head == nullptr || k == 0) return head;

        int len = 1;
        ListNode* p = head;
        while (p->next) { // 求长度
            len++;
            p = p->next;
        }
        k = len - k % len;

        p->next = head; // 首尾相连
        for(int step = 0; step < k; step++) {
            p = p->next;  //接着往后跑
        }
        head = p->next; // 新的首节点
        p->next = nullptr; // 断开环
        return head;
    }
};

  1. 这道题目的核心一句话是:取还是不取。
    如果当前取,则index+1作为参数。如果当前不取,则任用index作为参数。

  2. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。

  3. 博主您好,这是一个内容十分优秀的博客,而且界面也非常漂亮。但是为什么博客的响应速度这么慢,虽然博客的主机在国外,但是我开启VPN还是经常响应很久,再者打开某些页面经常会出现数据库连接出错的提示

  4. #!/usr/bin/env python
    def cou(n):
    arr =
    i = 1
    while(i<n):
    arr.append(arr[i-1]+selfcount(i))
    i+=1
    return arr[n-1]

    def selfcount(n):
    count = 0
    while(n):
    if n%10 == 1:
    count += 1
    n /= 10
    return count