- 1 ListNode* rotateRight(ListNode* head, int k) {
- 2 /* 特殊情况判断 */
- 3 if (head == nullptr || head->next == nullptr || k == 0) {
- 4 return head;
- 5 }
- 6
- 7 /* 增加虚拟头节点 */
- 8 ListNode* dummy = new ListNode(0);
- 9 dummy->next = head;
- 10
- 11 /* 获取链表长度 */
- 12 int len = 0;
- 13 for (ListNode* node = head; node != nullptr; node = node->next) {
- 14 len++;
- 15 }
- 16
- 17 k %= len;
- 18 /* 判断 k 是否是 len 的整数倍 */
- 19 if (k == 0) {
- 20 return head;
- 21 }
- 22
- 23 /* 获取新链表的头尾节点 */
- 24 ListNode *fast = dummy, *slow = dummy;
- 25 for (int i = 0; i < k; ++i) {
- 26 fast = fast->next;
- 27 }
- 28 while (fast->next != nullptr) {
- 29 fast = fast->next;
- 30 slow = slow->next;
- 31 }
- 32 fast->next = head;
- 33 head = slow->next;
- 34 slow->next = nullptr;
- 35
- 36 /* 释放虚拟头节点 */
- 37 delete dummy;
- 38
- 39 return head;
- 40 }