给你一个链表的头节点 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
**(模拟)**O ( n ) O(n)O(n)
给你一个链表的头节点 head
,然后将链表每个节点向右移动 k
个位置。
样例:
如样例所示,head = [1,2,3,4,5]
,k = 2
,我们输出[4,5,1,2,3]
。下面来讲解模拟的做法。
假设链表的长度为n
,为了将链表每个节点向右移动 k
个位置,我们只需要将链表的后 k % n
个节点移动到链表的最前面,然后将链表的后k % n
个节点和前 n - k
个节点连接到一块即可。
具体过程如下:
1、首先遍历整个链表,求出链表的长度n
,并找出链表的尾节点tail
。
2、由于k
可能很大,所以我们令 k = k % n
,然后再次从头节点head
开始遍历,找到第n - k
个节点p
,那么1 ~ p
是链表的前 n - k
个节点,p+1 ~ n
是链表的后k
个节点。
3、接下来就是依次执行tail->next = head
,head = p->next
,p->next = nullptr
,将链表的后k
个节点和前 n - k
个节点拼接到一块,并让head
指向新的头节点(p->next
),新的尾节点即p
节点的next
指针指向null
。
4、最后返回链表的新的头节点head
。
时间复杂度分析: 链表一共被遍历两次,因此总的时间复杂度为O ( n ) O(n)O(n),n nn是链表的长度。
/** * 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 || !k) return head;
int n = 0; //链表的长度
ListNode* tail; //尾节点
for(ListNode* p = head; p ; p = p->next){
tail = p;
n++;
}
k %= n;
ListNode* p = head;
for(int i = 0; i < n - k - 1; i++) p = p->next; //找到链表的第n-k个节点
tail->next = head;
head = p->next;
p->next = nullptr;
return head; //返回新的头节点
}
};
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if(head == null|| k == 0) return head;
int n = 0; //链表的长度
ListNode tail = null; //尾节点
for(ListNode p = head; p != null ; p = p.next){
tail = p;
n++;
}
k %= n;
ListNode p = head;
for(int i = 0; i < n - k - 1; i++) p = p.next; //找到链表的第n-k个节点
tail.next = head;
head = p.next;
p.next = null;
return head; //返回新的头节点
}
}
原题链接:61. 旋转链表
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/weixin_45629285/article/details/120349254
内容来源于网络,如有侵权,请联系作者删除!