LeetCode_61_RotateList

1. 题目描述

Given a linked list, rotate the list to the right by k places, where k is non-negative.

Example 1:

Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL

Example 2:

Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL

2. 初解

和24题一样同样是考察链表的基本变换，不熟悉的情况下还是先画图理清思路：

首先找到链表的末尾的两个元素

这就是右移一次的过程，右移k次做k次循环即可。

你以为这就完了？奶衣乌。测试用例里居然出现了k=100000000000这种测试用例，好吧，算你狠，还是求一下模算一下最少需要右移几步把。。。

3. 代码

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct ListNode {
    int val;
    struct ListNode* next;
};

struct ListNode* rotateRight(struct ListNode* head, int k) {
    int count = 2;

    if (head == NULL || head->next == NULL) {  // 如果是空链表或者只有一个节点
        return head;
    }

    struct ListNode* prev = head;
    struct ListNode* curr = head->next;

    while (curr->next != NULL) {  // 找到最后两个元素
        curr = curr->next;
        prev = prev->next;
        count++;
    }

    k = k % count;

    for (int i = 0; i < k; i++) {
        prev->next = curr->next;
        curr->next = head;
        head = curr;

        while (curr->next != prev) {
            curr = curr->next;
        }
        prev = curr;
        curr = curr->next;
    }

    return head;
}

struct ListNode* CreatLL(int* arr, int size) {
    struct ListNode* dummyHead =
        (struct ListNode *)malloc(sizeof(struct ListNode));
    dummyHead->val = 0;
    dummyHead->next = NULL;
    struct ListNode* ptr = dummyHead;
    struct ListNode* tmp;

    for (int i = 0; i < size; i++) {
        tmp = (struct ListNode *)malloc(sizeof(struct ListNode));
        tmp->next = NULL;
        tmp->val = arr[i];
        ptr->next = tmp;
        ptr = ptr->next;
    }

    return dummyHead->next;
}

void printLL(struct ListNode* head) {
    struct ListNode* ptr = head;
    while (ptr) {
        printf("%d -> ", ptr->val);
        ptr = ptr->next;
    }
    putchar('\n');
}

int main() {
    int arr[] = { 0, 1, 2 };
    struct ListNode* head = CreatLL(arr, 3);
    printLL(head);
    head = rotateRight(head, 4);
    printLL(head);

    system("pause");
    return 0;
}

4. 改进

又到了LeetCode上的大佬使用降维打击的时候了。

我的原方法必须一次一次旋转，总共旋转k次，那有没有什么办法一次就旋转到位呢？答案当然是肯定的，只是需要变换一下思路。链表这种数据结构与字符串还有数组不同，把链表首尾相连成环，此时移动head的指向不就相当于旋转链表嘛！最后只要在对应的位置把环断开就得到了旋转后的链表

struct ListNode* rotateRight1(struct ListNode* head, int k) {
    if (head == NULL || head->next == NULL)
        return head;

    struct ListNode* tail = head;
    struct ListNode* newHead = head;
    int length = 1;

    // 先找到链表尾节点
    while (tail->next) {
        tail = tail->next;
        length++;
    }
    k %= length;

    // 链表成环
    tail->next = head;

    // 右移k次，相当于左移length - k次
    for (int i = 0; i < length - k; i++) {
        newHead = newHead->next;
        tail = tail->next;
    }

    tail->next = NULL;
    return newHead;
}

版权声明：若文中无特殊说明，则本文为原创文章，版权归 Syndicate 所有。

本文链接：https://laihaodong.cn/1990.html

所有原创文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。
您可以自由的转载和修改，但请务必注明文章来源并且不可用于商业目的。