当前位置： 移动技术网 > 科技>操作系统>windows > Leetcode61 旋转链表 中等

Leetcode61 旋转链表 中等

2020年08月10日  | 移动技术网科技  | 我要评论

题目：
在这里插入图片描述
思路：
仔细思考后旋转链表其实就相当于链表有个环，旋转后改变了头结点而已。
接下来可以找到一个关系，以题目示例1为例
假设5的next-1，也就是有一个环，那么移动后的头结点有什么规律
移动1，新头结点=倒数第一个=正数第5个
移动2，新头结点=倒数第二个=正数第4个
移动3，新头结点=倒数第三个=正数第3个
移动4，新头结点=倒数第四个=正数第2个
移动5=没移动
可以发现，新头结点=原链表正数第（链表长-移动步数+1）个
那么只需要头结点正向移动（链表长-移动步数）个就能到达新头结点

总结：

  1. 先修改链表成环
  2. 计算新头结点=正向移动多少步
  3. 把环撤销

代码：

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head == null){
            return null;
        }
        int len = 1;
        //pHead是辅助指针，接下来进行重复使用，不再新建额外ListNode对象
        ListNode pHead = head;
        //计算链表长
        while(pHead.next != null){
            len++;
            pHead = pHead.next;
        }
        //计算要移动多少步，对链表长求余即可，避免不必要的移动，减少移动次数
        int move = k % len;
        if(move == 0){
            return head;
        }
        //修改链表成环
        pHead.next = head;
        ListNode newHead;
        pHead = head;
        int moveCount = len-(move-1)-1;
        //找新头结点
        while(moveCount > 0){
            pHead = pHead.next;
            moveCount--;
        }
        newHead = pHead;
        len--;
        //移动len-1步到达末尾，把环去掉
        while(len > 0){
            pHead = pHead.next;
            len--;
        }
        pHead.next = null;
        return newHead;
    }
}

在这里插入图片描述

本文地址：https://blog.csdn.net/weixin_40208575/article/details/107878889

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网