旋转链表（C++解法）

解法）"/>

旋转链表（C++解法）

题目

给你一个链表的头节点 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]

C++代码

#include <iostream>
using namespace std;//创建链表结构体
struct ListNode {int val;ListNode* next;ListNode() :val(0), next(nullptr) {}ListNode(int x) :val(x), next(nullptr) {}ListNode(int x, ListNode* next) :val(x), next(next) {}
};/*
* 旋转链表问题
* 先算出链表的长度，将最后一个节点指向头节点形成环状链表
* 计算旋转后链表需要断开的位置，断开链表，返回新链表
*/
ListNode* rotateRight(ListNode* head, int k) {if (k == 0 || head == nullptr || head->next == nullptr) {return head;}int n = 1;ListNode* iter = head;while (iter->next != nullptr) {n++;iter = iter->next;}iter->next = head;int add = n - k % n;if (add == n) {return head;}while (add) {iter = iter->next;add--;}ListNode* ans = iter->next;iter->next = nullptr;return ans;
}int main() {ListNode* n1 = new ListNode(1);ListNode* n2 = new ListNode(2);ListNode* n3 = new ListNode(3);ListNode* n4 = new ListNode(4);ListNode* n5 = new ListNode(5);n1->next = n2;n2->next = n3;n3->next = n4;n4->next = n5;n5->next = nullptr;ListNode* head = n1;int k = 2;ListNode* ans = rotateRight(head, k);while (ans) {cout << ans->val << " ";ans = ans->next;}delete n1, n2, n3, n4, n5;return 0;
}

分析

旋转链表问题，先算出链表的长度，将最后一个节点指向头节点形成环状链表，计算旋转后链表需要断开的位置，断开链表，返回新链表。