LeeCode61 旋转链表
给一个链表的头结点,旋转链表,是每一个结点右移k个位置
输入:head = [1,2,3,4,5], k = 2
输出:[4,5,1,2,3]
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;
}
int n=1;
ListNode* cur = head;
while(cur->next != nullptr)
{
cur = cur->next;
n++;
}
// cur 当前指向链表尾节点
// cur->next = head; // 连接首位结点 //首尾节点连接写在这里,那么当step== n 的时候,会返回一个环形链表
int step = n- (k % n);
if( step == n)
{
return head;
}
cur->next = head; // 连接首位结点
while(step--)
{
cur = cur->next;
}
ListNode* res = cur->next;
cur->next = nullptr;
return res;
}
};