Loading...
墨滴

SuperMP

2021/04/20  阅读:16  主题:默认主题

Leetcode刷题 | 第110题:旋转链表

为什么要担心?如果努力了,担心不会让结果变得更好。

61. 旋转链表[1]

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

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

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

提示:链表中节点的数目在范围 [0, 500] 内,-100 <= Node.val <= 100,0 <= k <= 2 * 10^9


分析:设链表的长度为 cnt,实际上,仅需要向右移动 move = k % cnt 次即可。那么,链表将从索引 n - 1 - move 后断开,后半段的最后一个指针将指向前半段的首位置。为了完成上述操作:

  1. 计算链表的长度 cnt,计算过程中记录最后一个指针的地址 last;
  2. 根据索引 n - 1 - move 定位前半段最后一个位置和后半段的首位置;
  3. 前半段的最后一个位置指向 null;
  4. 后半段的最后一个指针 last 指向前半段的首位置 head;
  5. 后半段的首位置地址,即为旋转链表的头结点。

注意1:当 k = 0, k = cnt 或者 k % cnt == 0 时,旋转链表与原链表相同,无需处理。

注意2:(思路)也可以先将给定的链表连接成环,然后将指定位置断开。

JAVA代码:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || k == 0return head;
        int cnt = 0, move;
        ListNode dummy = head;
        ListNode last = null// 原链表的最后一个位置
        while (dummy != null) {
            if (dummy.next == null) last = dummy;
            dummy = dummy.next;
            ++cnt;
        }
        move = k % cnt; // 实际需要移动的次数
        if (move == 0return head;
        ListNode early_head = head;
        for (int i = 0; i < cnt - move - 1; i++) early_head = early_head.next;
        ListNode later_head = early_head.next;
        // System.out.println(later_head.val);
        early_head.next = null;
        last.next = head;
        return later_head;
    }
}
  • 时间复杂度为O(N);空间复杂度为O(1)。

参考资料

[1]

旋转链表: https://leetcode-cn.com/problems/rotate-list/

SuperMP

2021/04/20  阅读:16  主题:默认主题

作者介绍

SuperMP