我是靠谱客的博主 柔弱彩虹,这篇文章主要介绍双指针应用之旋转链表,现在分享给大家,希望可以做个参考。

题目描述

给定一个链表,旋转链表,将链表每个节点向右移动 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

分析

  1. 题意
    题目可以理解为:把指针移动到链表的倒数第k个结点,将倒数第(k-1)个结点的next改成null,再移动到链表最后一个结点,并使其指向初始的链表头节点。
  2. 判定移动类型
    假设链表长度=len;
    当k>len,则链表循环了k/len圈,到达的链表位置为k%len;
    当k<len,则链表循环0圈,到达位置为k;
    复制代码
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    int len = 0; // 链表长度 while (fast!=null){ len++; fast = fast.next; } k = k % len; fast = head; if (k == 0) return head; // 刚好转了 k/len 圈 /** * 找到链表的第 k%len 结点 */ while (k>0){ fast = fast.next; k--; }
  3. 采用双指针
    在这里我们使用了快慢指针原理,具体细节如下:
    我们得出k的值之后,先让快指针走k步;
    让快慢指针以相同速度一起移动,直到快指针到达尾结点,则慢指针所在位置就是链表中的倒数第k个结点,结合分析1即可得出。

具体代码

复制代码
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
34
35
36
37
/** 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; } */ public class Solution { public ListNode rotateRight(ListNode head, int k) { if (head == null) return null; ListNode fast = head; ListNode slow = head; ListNode reuslt = new ListNode(0); int len = 0; while (fast!=null){ len++; fast = fast.next; } k = k % len; fast = head; if (k == 0) return head; while (k>0){ fast = fast.next; k--; } while (fast.next!=null){ slow = slow.next; fast = fast.next; } fast.next = head; reuslt.next = slow.next; slow.next = null; return reuslt.next; } }

总结

巧妙利用双指针查找链表倒数第k个结点,申请一个新的链表,去除新链表的首节点,将修改后的就链表的首节点赋给新链表的首节点的next。

最后

以上就是柔弱彩虹最近收集整理的关于双指针应用之旋转链表的全部内容,更多相关双指针应用之旋转链表内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(60)

评论列表共有 0 条评论

立即
投稿
返回
顶部