LeetCode 61. 旋转链表

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

🔥 61. 旋转链表

思路分析

计算链表长度：遍历链表计算其长度。

连接成环：将链表尾部连接到头部，形成一个环。

找到新的头节点：根据 k 值计算新的头节点位置，并断开环。

参考代码

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

	// 1. 计算链表长度
	length := 1
	tail := head
	for tail.Next != nil {
		tail = tail.Next
		length++
	}

	// 2. 处理 k 的值
	k = k % length
	if k == 0 {
		return head
	}

	// 3. 连接成环
	tail.Next = head

	// 4. 找到新的头节点
	newTail := tail
	for i := 0; i < length-k; i++ {
		newTail = newTail.Next
	}
	newHead := newTail.Next

	// 5. 断开环
	newTail.Next = nil

	return newHead
}

🍏 点击查看 Java 题解

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) {
            return head;
        }
        int n = 1;
        ListNode cur = head;
        while (cur.next != null) {
            n++;
            cur = cur.next;
        }
        k = k % n;
        if (k == 0) {
            return head;
        }
        cur.next = head;
        for (int i = 0; i < n - k; i++) {
            cur = cur.next;
        }
        ListNode newHead = cur.next;
        cur.next = null;
        return newHead;
    }
}

本文作者: HGNULB

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