双指针应用之旋转链表

题目描述

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

   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即可得出。

具体代码

	/**
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。

最后

以上就是柔弱彩虹为你收集整理的双指针应用之旋转链表的全部内容，希望文章能够帮你解决双指针应用之旋转链表所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。