LeetCode_每日一题2

[61] 旋转链表

https://leetcode-cn.com/problems/rotate-list/description/

• algorithms
• Medium (40.61%)
• Likes: 496
• Dislikes: -
• Total Accepted: 139.3K
• Total Submissions: 337K
• Testcase Example: ‘[1,2,3,4,5]\n2’
• Source Code: 61.rotate-list.cpp

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

 

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]

示例 2：

输入：head = [0,1,2], k = 4
输出：[2,0,1]

 

提示：

• 链表中节点的数目在范围 [0, 500] 内
• -100 <= Node.val <= 100
• 0 <= k <= 2 * 109

方法1: 快慢指针, 首尾相连

思路: 旋转链表, 使节点移动, 可以将原链表转化为循环链表, 找到符合题意的头节点的位置即可

步骤:

• 设置两指针 fast 和 slow , fast 指针用于探索链表尾部, 构建循环链表, slow 指针用于确定头节点的位置
• 遍历链表, 记录链表长度(count), 找到链表尾部, 将尾部指向 head , 构建循环链表
• 移动 slow 指针, 题目要求将节点向右移动 k 个位置, 等价于将头指针向左移动 count - k 个位置, 为了避免 k > count 时多余的移动, 所以应向左移动 count - k % count 个位置

小Tips

• 遇到链表不要吝啬变量的使用, 比如本题, 使用双指针比使用单指针要快上不少

  • 单指针
    

  • 双指针
    

• 链表旋转, 移动 k 个位置, 向左移动等价于 头指针向右移动 k % count 个位置 , 向右移动等价于 头指针向右移动 count - k % count 个位置. count 为链表长度

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
            if(!head || k == 0) return head;
            ListNode* fast = head;
            ListNode* slow = head;
            int count = 1;
            while(fast->next){
                fast = fast->next;
                ++count;
            }
            fast->next = head;
            k = count - k % count;
            while(k-- > 1) slow = slow->next;
            head = slow->next;
            slow->next = nullptr;
            return head;
        }
};

复杂度分析:

• 时间复杂度: O(n) , 最多需要两次遍历
• 空间复杂度: O(1)