61. 旋转链表
给你一个链表的头节点 head
,旋转链表,将链表每个节点向右移动 k
个位置。
示例 1:
![](https://assets.leetcode.com/uploads/2020/11/13/rotate1.jpg)
输入:head = [1,2,3,4,5], k = 2 输出:[4,5,1,2,3]
示例 2:
![](https://assets.leetcode.com/uploads/2020/11/13/roate2.jpg)
输入:head = [0,1,2], k = 4 输出:[2,0,1]
提示:
- 链表中节点的数目在范围
[0, 500]
内 -100 <= Node.val <= 100
0 <= k <= 2 * 109
解析:
O(n)
就是先统计有多少结点n
k取模一下n
找到倒数第k个结点的前驱即可
/** * 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(head == nullptr) return head; int n = 0; ListNode* p = head; while(p) { n++; p = p->next; } k %= n; if(k == 0) return head; int cnt = 0; p = head; ListNode *q = head; while(q->next) { if(cnt == k) { p = p->next; } else cnt++; q = q->next; } ListNode *x = p->next; p->next = nullptr; q->next = head; head = x; return head; } };
标签:head,ListNode,val,int,next,链表,61,旋转 From: https://www.cnblogs.com/WTSRUVF/p/16645003.html