C++程链表的顺时针旋转

问题描述

给定一个链表和一个整数k，将链表旋转k次。例如，给定链表 1->2->3->4->5->NULL和 k = 3，链表变为3->4->5->1->2->NULL。假设k是非负的。

实现思路

首先，我们需要先分析一下题目的意思。将一个链表顺时针旋转k次，相当于将链表的最后k个元素放到链表的最前面。

接下来，我们来考虑一下如何实现。

首先，我们需要找到链表倒数第k个节点。这可以通过使用快慢指针来实现。我们先使快指针向前移动k步，然后让慢指针从头开始移动，当快指针到达链表的末尾时，慢指针所指向的节点就是倒数第k个节点。

然后，我们需要将链表的最后k个节点放到链表的最前面。这可以通过将链表的最后一个节点与倒数第k+1个节点相连，然后将倒数第k个节点设为链表的头节点来实现。

最后，我们需要将倒数第k+1个节点设为链表的尾节点，也就是将它所指向的节点的next指针设置为NULL。

代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (head == NULL || head->next == NULL || k == 0) {
            return head;
        }
        int length = 1;
        ListNode* tail = head;
        while (tail->next != NULL) {
            tail = tail->next;
            length++;
        }
        k %= length;
        if (k == 0) {
            return head;
        }
        ListNode* fast = head;
        ListNode* slow = head;
        for (int i = 0; i < k; i++) {
            fast = fast->next;
        }
        while (fast->next != NULL) {
            fast = fast->next;
            slow = slow->next;
        }
        ListNode* new_head = slow->next;
        slow->next = NULL;
        tail->next = head;
        return new_head;
    }
};

注：这里快慢指针指的是指针所指向链表的节点，而不是指针本身。