面试经典算法14-旋转链表

LeetCode.61

问题描述

给你一个链表的头节点 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. 计算链表的长度，并找到链表的尾节点，同时将链表形成一个循环链表。
2. 计算实际需要移动的步数 k = k % 链表长度，因为如果 k 大于链表长度，实际上是重复一整轮的旋转操作。
3. 找到新链表的尾节点和头节点的位置，并将尾节点指向 nullptr，形成新的链表。

图解

这里根据示例一给大家做一个图解。

1. 计算链表的长度，并找到链表的尾节点，同时将链表形成一个循环链表。

2. 计算实际需要移动的步数 k = k % 链表长度，因为如果 k 大于链表长度，实际上是重复一整轮的旋转操作。

3. 找到新链表的尾节点和头节点的位置，并将尾节点指向 nullptr，形成新的链表

即：

4. 返回newHead即可。

参考代码

C++

#include <iostream>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (!head || !head->next || k == 0) return head; // 如果链表为空或只有一个节点，或者 k 为 0，直接返回原链表

        int length = 1; // 计算链表长度
        ListNode* tail = head;
        while (tail->next) {
            tail = tail->next;
            length++;
        }

        k = k % length; // 计算实际需要移动的步数

        if (k == 0) return head; // 如果 k 等于 0，直接返回原链表

        ListNode* newTail = head;
        for (int i = 0; i < length - k - 1; i++) {
            newTail = newTail->next;
        }

        ListNode* newHead = newTail->next;
        newTail->next = nullptr;
        tail->next = head;

        return newHead;
    }
};

// 创建链表
ListNode* createList(std::vector<int>& nums) {
    if (nums.empty()) return nullptr;
    ListNode* head = new ListNode(nums[0]);
    ListNode* cur = head;
    for (int i = 1; i < nums.size(); ++i) {
        cur->next = new ListNode(nums[i]);
        cur = cur->next;
    }
    return head;
}

// 输出链表
void printList(ListNode* head) {
    ListNode* cur = head;
    while (cur) {
        std::cout << cur->val << " ";
        cur = cur->next;
    }
    std::cout << std::endl;
}

int main() {
    std::vector<int> nums = {1, 2, 3, 4, 5};
    int k = 2;

    // 创建链表
    ListNode* head = createList(nums);

    // 旋转链表
    Solution solution;
    ListNode* newHead = solution.rotateRight(head, k);

    // 输出旋转后的链表
    printList(newHead);

    return 0;
}

Java

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || k == 0) return head;

        // 计算链表长度并找到尾节点
        int len = 1;
        ListNode tail = head;
        while (tail.next != null) {
            tail = tail.next;
            len++;
        }

        // 计算实际需要旋转的次数
        k = k % len;
        if (k == 0) return head; // 如果 k 是链表长度的倍数，不需要旋转

        // 找到倒数第 k+1 个节点，作为新的尾节点
        ListNode newTail = head;
        for (int i = 0; i < len - k - 1; i++) {
            newTail = newTail.next;
        }

        // 旋转链表
        ListNode newHead = newTail.next;
        newTail.next = null; // 断开环
        tail.next = head; // 将原链表接到尾部

        return newHead;
    }
}

Python

class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if not head or k == 0:
            return head

        # 计算链表长度并找到尾节点
        len = 1
        tail = head
        while tail.next:
            tail = tail.next
            len += 1

        # 计算实际需要旋转的次数
        k = k % len
        if k == 0:
            return head  # 如果 k 是链表长度的倍数，不需要旋转

        # 找到倒数第 k+1 个节点，作为新的尾节点
        new_tail = head
        for _ in range(len - k - 1):
            new_tail = new_tail.next

        # 旋转链表
        new_head = new_tail.next
        new_tail.next = None  # 断开环
        tail.next = head  # 将原链表接到尾部

        return new_head