旋转链表（leetcode）

61. 旋转链表

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

提示：

• 链表中节点的数目在范围 [0, 500] 内

• -100 <= Node.val <= 100

• 0 <= k <= 2 * 109

原题链接：61. 旋转链表

---

思路：闭合为环

 

        1.设有n个节点，当k=xn(x=1.2.3.4.....)时，链表不变，等价求余运算，

即移动k%n位。

        2.将该链表改为环：遍历链表，找到尾节点，与头节点相连，并算出链表长度n。

        3.右移k个位置 =>等价于环旋转k个节点 => 以（n-k+1）位置 为头节点，切环为链。

/**
  * Definition for singly-linked list.
  * 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) {}
  * };
  */
 class Solution {
 public:
     ListNode* rotateRight(ListNode* head, int k) {
         if(k==0||head==nullptr||head->next==nullptr) return head;
         auto p=head;
         int n=0;
         while(p&&p->next) {n++;p=p->next;} //结束循环时是p位置是尾节点
         p = p->next = head;   //将链表变为环。p->next = head；
                                         //  p = p->next；
         k %= ++n;              //++n;
                               //k %= n;
         for(int i=0;p&&inext; //inext;
         p->next=nullptr;
         return list;
 ​
     }
 };

实际编码中会遇到的问题：

        1.while(p&&p->next) {n++;p=p->next;} 注意p在结束循环时的位置，指向null，所以应该让停在尾节点。

        2.for(int i=0;p&&inext; 在切环时，应先找到当作头节点之前的位置，在本题中为（n-k）位置， 另，注意p在结束时循环的位置，所以应该循环n-k-1次 p就到了n-k位置。

---