LeetCode //C - 61. Rotate List-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode //C - 61. Rotate List。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

61. Rotate List

Given the head of a linked list, rotate the list to the right by k places.

Example 1:

LeetCode //C - 61. Rotate List,LeetCode,leetcode,c语言,算法

Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]

Example 2:

LeetCode //C - 61. Rotate List,LeetCode,leetcode,c语言,算法

Input: head = [0,1,2], k = 4
Output: [2,0,1]

Constraints:

The number of nodes in the list is in the range [0, 500].
-100 <= Node.val <= 100
$0 <= k <= 2 * 10^9$

From: LeetCode
Link: 61. Rotate List
文章来源地址https://www.toymoban.com/news/detail-691991.html

Solution:

Ideas：

Find the Length: First, traverse the list to find its length n.
Calculate Effective Rotation: Since rotating a list of length n places is the same as not rotating it at all, we only need to rotate k mod n places.
Find New Head: Traverse the list to the (n−k mod n)th node. This will be the new tail after rotation.
Perform Rotation: Update the next pointer of the new tail to NULL and set the next pointer of the old tail to the old head.

Code:

struct ListNode* rotateRight(struct ListNode* head, int k) {
    if (head == NULL || k == 0) {
        return head;
    }
    
    // Step 1: Find the length of the list
    int n = 1;
    struct ListNode *tail = head;
    while (tail->next != NULL) {
        n++;
        tail = tail->next;
    }
    
    // Step 2: Calculate the effective number of rotations needed
    k = k % n;
    if (k == 0) {
        return head;
    }
    
    // Step 3: Find the new head and tail
    struct ListNode *new_tail = head;
    for (int i = 0; i < n - k - 1; i++) {
        new_tail = new_tail->next;
    }
    struct ListNode *new_head = new_tail->next;
    
    // Step 4: Perform the rotation
    new_tail->next = NULL;
    tail->next = head;
    
    return new_head;
}