网站链接: element-ui dtcms
当前位置: 首页 > 技术博文  > 技术博文

2021-06-28旋转链表

2021/6/28 22:19:25 人评论

leetcode每日一题之旋转链表 **题目链接:**https://leetcode-cn.com/problems/rotate-list/ 题目描述: 给你一个链表的头节点 head ,旋转链表,将链表每个节点向右移动 k 个位置。 例子: 输入:head [1…

leetcode每日一题之旋转链表

**题目链接:**https://leetcode-cn.com/problems/rotate-list/

题目描述:

给你一个链表的头节点 head ,旋转链表,将链表每个节点向右移动 k 个位置。

例子:

输入:head = [1,2,3,4,5], k = 2
输出:[4,5,1,2,3]

输入:head = [0,1,2], k = 4
输出:[2,0,1]

解法:

以示例1为例 1->2->3->4->5,k=2,那么移动完就是:
4->5->1->2->3
移动一次的时候是 5->1->2->3->4,移动两次就是4->5->1->2->3。
看出什么端倪了吗?
关键点就是k,如果移动一次就相当于将倒数第一个元素1移到链表开头,如果移动两次就相当于将倒数第二和倒数第一个元素2和1移动到链表开头。
所以这题的关键是要找到倒数第k个节点。
在这之前我们还需要处理一些细节:
当k等于链表总长时,就相当于移动0次,也就是啥也不用做直接返回就行了。如果k>链表总长,比如k=7时,结果仍然是5->4->3->2->1。
所以我们要先对k取模,取模后的k范围应该是:
1<=k<=链表总长-1
找到倒数第k个节点4,然后将链表的尾部指向开头
在这里插入图片描述

再将节点4前面一个3的next指向null,一定要断开,否则链表就成环状啦
在这里插入图片描述

最后返回新的头结点4就可以了
在这里插入图片描述

代码如下:

    public ListNode rotateRight(ListNode head, int k) {
            if (head == null || k <= 0) {
                return head;
            }
            //创建一个特殊节点,快指针,慢指针,统计节点个数的cur
            ListNode p = new ListNode(-1);
            p.next = head;
            ListNode cur = p;
            ListNode low = p;
            ListNode fast = p;
            int n = 0;
            //统计链表个数
            while (cur.next != null) {
                cur = cur.next;
                ++n;
            }
            //边界条件不用忘记处理了
            //其实有这段最上面的head==null可以省略
            if (n == 0 || k % n == 0) {
                return head;
            }
            //还有一个边界条件不要忘了,k可能大于n,所以要取模
            k = k % n;
            //快指针先移动k步
            while (fast.next != null && k > 0) {
                fast = fast.next;
                --k;
            }
            //快指针,慢指针一起移动,找到需要切割的点
            while (fast.next != null) {
                low = low.next;
                fast = fast.next;
            }
            //改变链表的指向关系,注意这里的步骤不要乱了
            //先让fast节点指向head(也就是p.next)
            //再是head(也就是p.next)指向low的下一个节点
            //这两步如果弄反了就会出现节点丢失了
            //最后不要忘记将low.next置空
            fast.next = p.next;
            p.next = low.next;//为了返回使用,结合着图看
            low.next = null;
            return p.next;
        }
    

=======================================================================================

下面是看懂之后自己写的一遍代码:

    public ListNode rotateRight2(ListNode head, int k) {
            //
            if (head == null || head.next == null || k <= 0) {
                return head;
            }
            //首先统计链表个数,定义一个假节点
            ListNode dummy = new ListNode(-1);
            dummy.next = head;
            ListNode p = dummy;
            //快慢指针是为了查找倒数第k个节点
            ListNode slow = dummy;
            ListNode fast = dummy;
            int n = 0;//链表元素个数
            while (p.next != null) {
                p = p.next;
                n++;
            }
            if (n == 0 || k % n == 0) {
                return head;
            }
    //        k = n % k;这里自己写的时候出现了误解
            k = k % n;//k可能大于n
            //先让块指针走k步
            while (fast.next != null && k > 0) {
                fast = fast.next;
                k--;
            }
            while (fast.next != null) {
                slow = slow.next;
                fast = fast.next;
            }
            fast.next = dummy.next;
            dummy.next = slow.next;
            slow.next = null;
            return dummy.next;
        }

总之,这个题目还是挺好的,因为我不喜欢动手,因此又是没有想起来,只是用到了之前的找倒数第k个节点,相当于又复习了一遍。

参考:配图以及讲解都来自公众号大话算法

相关资讯

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?