C language force buckle question 61 of the rotating list. Double ended queue and construction of circular linked list

Give you a list of the head node head , Rotate the list , Move each node of the list to the right k A place .

Example 1：

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

Example 2：

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

Tips ：

    The number of nodes in the linked list is in the range [0, 500] Inside
    -100 <= Node.val <= 100
    0 <= k <= 2 * 109

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/rotate-list
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Method 1 ：

Note that the length of the given linked list is n, Notice how many times you move to the right k≥nk  when , We just need to move to the right k mod nk  Next time . Because each nnn Every move will change the linked list to its original state . So we can know , The last node of the new linked list is the... Of the original linked list (n−1)−(k mod n)(n - 1) Nodes （ from 0 Start counting ）.

such , We can first connect the given linked list into a ring , Then disconnect the specified location .

In the specific code , We first calculate the length of the linked list nnn, And find the end node of the linked list , Connect it to the head node . In this way, we get the linked list closed as a ring . Then we find the last node of the new linked list （ That is, the... Of the original linked list (n−1)−(k mod n) Nodes ）, Break the linked list currently closed as a ring , We can get the results we need .

Specially , When the length of the linked list is not greater than 1, perhaps k by n A multiple of the , The new linked list will be the same as the original linked list , We don't need to do anything .

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++;
	}
	// Connect the end of the list with the head of the chain , Circular linked list 
	tail->next = head;
	// The linked list moves backward k Step 
	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;
}

Method 2 ：

As the example shows ,head = [1,2,3,4,5],k = 2, We output [4,5,1,2,3]. Let's explain the practice of simulation .

Suppose the length of the linked list is n, In order to move each node of the linked list to the right k A place , We just need to put the back of the linked list k % n A node moves to the front of the linked list , Then put the back of the linked list k % n Nodes and front n - k One node can be connected to one piece .

The specific process is as follows ：

1、 First, traverse the whole linked list , Find the length of the list n, And find the tail node of the linked list tail.

 

2、 because k It could be very big , So we make k = k % n, Then start from the beginning again head To traverse the , Find No n - k Nodes p, that 1 ~ p Is the front of the linked list n - k Nodes ,p+1 ~ n It is the back of the linked list k Nodes .

3、 The next step is to execute tail->next = head,head = p->next,p->next = nullptr, Put the back of the linked list k Nodes and front n - k A node is spliced into a piece , And let head Point to the new head node (p->next), The new tail node is p Node next Pointer to null.

4、 Finally, return the new head node of the linked list 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;
}