LeetCode 61. 旋转链表

Categories:

Tags:

题目描述
思路分析
1. 解法一：成环后断开（推荐）
相似题目

题目描述

✅ 61. 旋转链表

思路分析

解法一：成环后断开（推荐）

核心思路：

先遍历链表求长度 n，并找到尾节点。

将尾节点连接到头节点形成环。

计算新的尾节点位置 n - k % n - 1，断开环得到新头。

复杂度分析：

时间复杂度：O(n)，其中 n 表示链表长度。

空间复杂度：O(1)，仅使用常数额外空间。

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

        int n = 1;
        ListNode tail = head;
        while (tail.next != null) {
            tail = tail.next;
            n++;
        }

        int step = n - k % n;
        if (step == n) {
            return head;
        }

        tail.next = head;
        ListNode newTail = head;
        for (int i = 1; i < step; i++) {
            newTail = newTail.next;
        }
        ListNode newHead = newTail.next;
        newTail.next = null;
        return newHead;
    }
}

func rotateRight(head *ListNode, k int) *ListNode {
	if head == nil || head.Next == nil || k == 0 {
		return head
	}

	n := 1
	tail := head
	for tail.Next != nil {
		tail = tail.Next
		n++
	}

	step := n - k%n
	if step == n {
		return head
	}

	tail.Next = head
	newTail := head
	for i := 1; i < step; i++ {
		newTail = newTail.Next
	}
	newHead := newTail.Next
	newTail.Next = nil
	return newHead
}

相似题目

题目	难度	考察点
206. 反转链表	简单	链表操作
92. 反转链表 II	中等	链表操作
24. 两两交换链表中的节点	中等	链表操作
143. 重排链表	中等	链表操作
61. 旋转链表	中等	链表操作

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/42871102