旋转链表

发表于
本文字数： 908 阅读时长 ≈ 1 分钟

LeetCode每日一题，61. Rotate List

先看题目描述

6xBz59.png

大意就是给定一个链表和一个整数 k，让我们将链表顺时针旋转 k 次

算法和思路

这题挺简单，只要拿笔画一画，一下就做出来了

算法流程

  • 遍历一次链表得到链表长度 len 和尾节点 tail
  • 令 k = len - k % len，此时的第 k - 1 个节点就是旋转后链表的尾节点
  • 令第 k - 1 个节点的 next 为空，tail 的 next 指向 head，就完成了旋转链表的操作

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null) {
            return head;
        }
        ListNode cur = head;
        ListNode pre = head;
        int len = 1;
        while (cur.next != null) {
            cur = cur.next;
            len++;
        }
        ListNode tail = cur;
        k = k % len;
        if (k == 0) {
            return head;
        }
        k = len - k;
        cur = head;
        for (int i = 0; i < k; i++) {
            pre = cur;
            cur = cur.next;
        }
        pre.next = null;
        tail.next = head;
        return cur;
    }
}