​LeetCode刷题实战61:旋转链表

程序IT圈

共 1703字,需浏览 4分钟

 ·

2020-10-11 12:38

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 旋转链表,我们先来看题面:

https://leetcode-cn.com/problems/rotate-list/

Given a linked list, rotate the list to the right by k places, where k is non-negative.

题意

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


解题

https://segmentfault.com/a/1190000016302210
链表的题目,其实就是在考指针交换,这个题目先让链表连成一个环,然后再切开就可以完成了,如下图所示:


public class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }

        int count = 1;
        ListNode cur = head;
        while (cur.next != null) {
            count++;
            cur = cur.next;
        }
        k = k % count;
        if (k == 0) {
            return head;
        }
        cur.next = head;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode prev = dummy;
        for (int i = 0; i < count - k; i++) {
            prev = prev.next;
        }
        cur = prev.next;
        prev.next = null;
        return cur;
    }
}


好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力。


上期推文:


LeetCode1-50题汇总,速度收藏!
LeetCode刷题实战51:N 皇后
LeetCode刷题实战52:N皇后 II
LeetCode刷题实战53:最大子序和
LeetCode刷题实战54:螺旋矩阵
LeetCode刷题实战55:跳跃游戏
LeetCode刷题实战56:合并区间
LeetCode刷题实战57:插入区间
LeetCode刷题实战58:最后一个单词的长度
LeetCode刷题实战59:螺旋矩阵 II
LeetCode刷题实战60:第k个排列


浏览 31
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报