ToB企服应用市场:ToB评测及商务社交产业平台

标题: 算法与数据结构（旋转链表） [打印本页]

---

作者: 没腿的鸟    时间: 5 天前
标题: 算法与数据结构（旋转链表）
题目

思绪

每个节点向右移动k个位置，其实就是从头开始遍历，将n-k个节点顺序插入到链表的尾部。

如上图所示的示例1，先将1插入到5的后面，再将2插入到1的后面，最后将3插入到2的后面即可。
代码详解

定义一个cur变量用来遍历到最后一个节点，方便后面的插入，a为移动节点的个数，iter变量从头开始遍历，将每个节点不断地今后插入。插入完毕后，将最后一个节点的next指向空即可。
iter即为新链表的头结点
代码

1. class Solution {
2. public:
3.     ListNode* rotateRight(ListNode* head, int k) {
4.         if(head==nullptr || head->next==nullptr)
5.             return head;
6.         ListNode* cur = head;
7.         int n = 1;
8.         while(cur->next)
9.         {
10.             n++;
11.             cur = cur->next;
12.         }
13.         int a = n - k%n;
14.         ListNode* iter = head;
15.         while(a--)
16.         {
17.             cur->next = iter;
18.             cur = iter;
19.             iter = iter->next;
20.         }
21.         cur->next = nullptr;
22.         return iter;
23.     }
24. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4