C语言力扣第61题之旋转链表。双端队列与构造循环链表

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]

示例 2：

输入：head = [0,1,2], k = 4
输出：[2,0,1]

提示：

    链表中节点的数目在范围 [0, 500] 内
    -100 <= Node.val <= 100
    0 <= k <= 2 * 109

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/rotate-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法一：

记给定链表的长度为 n，注意到当向右移动的次数 k≥nk  时，我们仅需要向右移动 k mod nk  次即可。因为每 nnn 次移动都会让链表变为原状。这样我们可以知道，新链表的最后一个节点为原链表的第 (n−1)−(k mod n)(n - 1)个节点（从 0 开始计数）。

这样，我们可以先将给定的链表连接成环，然后将指定位置断开。

具体代码中，我们首先计算出链表的长度 nnn，并找到该链表的末尾节点，将其与头节点相连。这样就得到了闭合为环的链表。然后我们找到新链表的最后一个节点（即原链表的第 (n−1)−(k mod n)个节点），将当前闭合为环的链表断开，即可得到我们所需要的结果。

特别地，当链表长度不大于 1，或者 k 为 n 的倍数时，新链表将与原链表相同，我们无需进行任何处理。

typedef struct ListNode ListNode;

struct ListNode *rotateRight(struct ListNode *head, int k) {

	if (!head) {
		return head;
	}

	int length = 1;
	ListNode *tail = head;
	ListNode *temp = head;
	while (tail->next) {
		tail = tail->next;
		length++;
	}
	//把链表尾和链表头相连,循环链表
	tail->next = head;
	//链表向后移动k步
	k = k % length;

	for (int i = 0; i < length - k; ++i) {
		temp = temp->next;
	}

	ListNode *res = temp;
	for (int i = 0; i < length - 1; ++i) {
		temp = temp->next;
	}

	temp->next = NULL;

	return res;
}

方法二：

如样例所示，head = [1,2,3,4,5]，k = 2，我们输出[4,5,1,2,3]。下面来讲解模拟的做法。

假设链表的长度为n，为了将链表每个节点向右移动 k 个位置，我们只需要将链表的后 k % n个节点移动到链表的最前面，然后将链表的后k % n个节点和前 n - k个节点连接到一块即可。

具体过程如下：

1、首先遍历整个链表，求出链表的长度n，并找出链表的尾节点tail。

 

2、由于k可能很大，所以我们令 k = k % n，然后再次从头节点head开始遍历，找到第n - k个节点p，那么1 ~ p是链表的前 n - k个节点，p+1 ~ n是链表的后k个节点。

3、接下来就是依次执行 tail->next = head，head = p->next，p->next = nullptr，将链表的后k个节点和前 n - k个节点拼接到一块，并让head指向新的头节点(p->next)，新的尾节点即p节点的next指针指向null。

4、最后返回链表的新的头节点head。

struct ListNode* rotateRight(struct ListNode* head, int k) {
	struct ListNode* arr[501];
	struct ListNode *dummy = head;
	struct ListNode *temp = NULL;
	int count = 0;
	while (dummy != NULL) {
		arr[count++] = dummy;
		dummy = dummy->next;
	}
	if (count <= 1) {
		return head;
	}
	k %= count;
	arr[count - 1]->next = arr[0];
	temp = arr[count - 1 - k]->next;
	arr[count - 1 - k]->next = NULL;
	return temp;
}