题解 | #旋转链表#

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* rotateLinkedList(ListNode* head, int k) {
        // write code here
        if (!head || !head->next || k == 0) return head;

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

        cout << len << endl;
        // 首尾相连成环
        tail->next = head;

        // 计算移动距离
        k = k % len;
        if (k == 0) {
            tail->next = nullptr; // 还从原来的位置断开
            return head;
        }

        // 找到新的尾部，移动 (len - k) 步
        int stepsToNewTail = len - k;
        ListNode* newTail = head;
        for (int i = 0; i < stepsToNewTail - 1; ++i) {
            newTail = newTail->next;
        }

        // 从新的尾部后面这里断开
        ListNode* newHead = newTail->next;
        newTail->next = nullptr;

        return newHead;
    }
};