给定一个链表,旋转链表,将链表每个节点向右移动 k 个位置,其中 k 是非负数。 示例 1:
输入: 1->2->3->4->5->NULL, k = 2 输出: 4->5->1->2->3->NULL 解释: 向右旋转 1 步: 5->1->2->3->4->NULL 向右旋转 2 步: 4->5->1->2->3->NULL
示例 2:
输入: 0->1->2->NULL, k = 4 输出: 2->0->1->NULL 解释: 向右旋转 1 步: 2->0->1->NULL 向右旋转 2 步: 1->2->0->NULL 向右旋转 3 步: 0->1->2->NULL 向右旋转 4 步: 2->0->1->NULL
分析 本题的话就是题意比较清晰,就是旋转链表将链表进行右移动k个。
但是具体的处理上可能存在时间复杂度的差距,比如你可以第一次遍历到结尾,然后构成一个循环链表不停遍历找到合适的位置。或者先遍历一次到尾,然后再找到需要移动的位置去进行操作,但是这样都避免不了循环两次。
那本题采用什么方法呢?使用快慢指针,快指针先走k步,然后快慢指针一起走,一直到快指针走到尾。 执行以下操作即可:
但是过程可能没那么顺畅,很可能k比整个链表的长度还大,所以可能k没跑完就遍历结束了,这种情况也不用担心,当fast到底的时候可以通过一次计算算出真实有效的移动位数。比如如果链表长10让你右移59,69,79这些和移动9次是一样的,所以只需要slow再次移动到真实有效的地方即可。
实现的代码为:
public ListNode rotateRight(ListNode head, int k) {
if(k==0||head==null)return head;
ListNode fast=head;
ListNode slow=head;
for(int i=0;i<k;i++)
{
if(fast.next==null)//说明超出范围了 但是此时知道最大长度了
{
k=(k)%(i+1);
if(k==0)return head;
for(int j=0;j<i-k;j++)
{
slow=slow.next;
}
break;
}
fast=fast.next;
}
while (fast.next !=null) {
fast=fast.next;
slow=slow.next;
}
fast.next=head;
ListNode team=slow.next;
slow.next=null;
return team;
}
原创不易,bigsai请你帮两件事帮忙一下:
star支持一下, 您的肯定是我在平台创作的源源动力。
微信搜索「bigsai」,关注我的公众号,不仅免费送你电子书,我还会第一时间在公众号分享知识技术。加我还可拉你进力扣打卡群一起打卡LeetCode。
记得关注、咱们下次再见!
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。