当前位置：首页 > article >正文

LeetCode 61. 旋转链表

article 2025/3/4 15:25:57

题目描述

分析

grq：关于链表结点的修改顺序：改前先用，用后就改。
将每个结点向右移动k个位置，实际上就是将后k个结点连接到头部。这道题目是不需要dummy结点的。整体分析如下：
在这里插入图片描述

首先要获得整个链表也是后k个结点的尾结点。由于整个是n个结点，除掉后k个结点后还有n-k个结点，要修改指针首先要跳到倒数第k+1个结点（正数第n-k个结点），从第一个结点跳n-k-1次就可以到达。之后就是指针的修改：

尾结点指向头结点
倒数第k个变为新的头结点
倒数第k+1（正数第n-k）个结点变为尾结点指向null，

代码（Java）

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null) return head;
        ListNode tail = head;
        // 先求出链表长度
        int n = 1;
        while (tail.next != null) {
            n ++;
            tail = tail.next;
        }

        k %= n;
        if (k == 0) return head;

        ListNode cur = head;
        // 倒数第k+1个结点成了尾结点
        for (int i = 0; i < n - k - 1; i ++) cur = cur.next;
        
        tail.next = head;
        head = cur.next;
        cur.next = null;
        return head;
    }
}