欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  科技

Leetcode61 旋转链表 中等

程序员文章站 2022-06-18 19:41:39
题目:思路:仔细思考后旋转链表其实就相当于链表有个环,旋转后改变了头结点而已。接下来可以找到一个关系,以题目示例1为例假设5的next-1,也就是有一个环,那么移动后的头结点有什么规律移动1,新头结点=倒数第一个=正数第5个移动2,新头结点=倒数第二个=正数第4个移动3,新头结点=倒数第三个=正数第3个移动4,新头结点=倒数第四个=正数第2个移动5=没移动可以发现,新头结点=原链表正数第(链表长-移动步数+1)个那么只需要头结点正向移动(链表长-移动步数)个就能到达新头结点总结:...

题目:
Leetcode61 旋转链表 中等
思路:
仔细思考后旋转链表其实就相当于链表有个环,旋转后改变了头结点而已。
接下来可以找到一个关系,以题目示例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;
    }
}

Leetcode61 旋转链表 中等

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

相关标签: 算法