LeetCode刷题实战61:旋转链表

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

本文分享自微信公众号 - 程序IT圈(DeveloperIT)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

评论

暂无评论