61. 旋转链表
给你一个链表的头节点 head ,旋转链表,将链表每个节点向右移动 k 个位置。
示例 1:
![](https://assets.leetcode.com/uploads/2020/11/13/rotate1.jpg)
1 2
| 输入:head = [1,2,3,4,5], k = 2 输出:[4,5,1,2,3]
|
示例 2:
![](https://assets.leetcode.com/uploads/2020/11/13/roate2.jpg)
1 2
| 输入:head = [0,1,2], k = 4 输出:[2,0,1]
|
提示:
链表中节点的数目在范围 [0, 500] 内
-100 <= Node.val <= 100
0 <= k <= 2 * 10^9
对于这题我们可以直接先将链表连成环,然后断开旋转后的头尾结点就行了。
比如 1->2->3->4->5 我们将 5连上1 ,然后再将3,4断开,这样我们就得到了一个旋转后的链表。
代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
|
class Solution { public: ListNode* rotateRight(ListNode* head, int k) { if(head == NULL)return NULL; int len = 1; ListNode * p = head; while(p->next!=NULL){ p = p->next; len++; } k=k%len; if(k==0)return head;
ListNode * q = head; for(int i = 0 ; i < len - k - 1 ; i++){ q = q->next; } p->next = head; ListNode * newHead = q->next; q->next = NULL; return newHead; } };
|