image.png

思路1：连接成环

  • 一开始的思路是双指针，但LC61.旋转链表 - 图2如果很大，速度上不去，所以必须要读出初始链表的长度LC61.旋转链表 - 图3，这一步不得不做
  • 将tail和head连接起来，变成环
  • 找到合适的位置断开，LC61.旋转链表 - 图4#card=math&code=step%20%3D%20list%5C_size%20-%20%28k%20%5C%25%20list%5C_size%29&id=vCyRz)

    代码1：

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode() : val(0), next(nullptr) {}
  7.  *     ListNode(int x) : val(x), next(nullptr) {}
  8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
  9.  * };
  10.  */
  11. class Solution {
  12. public:
  13.     ListNode* rotateRight(ListNode* head, int k) {
  14.         // 虽然我不愿意去读整个链表的长度，但是出于简化计算的目的，还是需要这么干的
  15.         if (!head || k <= 0) {
  16.             return head;
  17.         }
  19.         int list_size = 1;
  20.         ListNode* ptr_1 = head;
  21.         while (ptr_1->next) {
  22.             ptr_1 = ptr_1->next;
  23.             list_size++;
  24.         }
  25.         ptr_1->next = head;
  27.         int step = list_size - (k % list_size);
  28.         while (step--) {
  29.             ptr_1 = ptr_1->next;
  30.         }
  32.         ListNode* new_head = ptr_1->next;
  33.         ptr_1->next = nullptr;
  35.         return new_head;
  36.     }
  37. };