“This is the second day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”

[B] [C] [D]

Give you the head of a linked list, rotate the list, and move each node k positions to the right.

Example 1:

Input: head = [1,2,3,4,5], k = 2 output: [4,5,1,2,3]Copy the code

Example 2:

Input: head = [0,1,2], k = 4Copy the code

Tip:

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

Take a look at the following chart:

When we join the list into a loop, if k is 1, we just unhook the loop at 4 and return to the head node

If k is 2, we just unhook the ring at 3 and return to the head node

The answer to this question is as follows:

  1. Depending on the problem, the linked list might be empty,kIt could be 0, so we’re going to specifically evaluate if the list is empty ork=0, directly return the head node
  2. Gets the list lengthlenIf thekislenSo we don’t really need to flip the list, otherwise it willk 对 lenMod, the number of flips we have to do
  3. Join a linked list into a loop
  4. Find the location of the disassembled ring, get the head node after the disassembled ring, then disassemble the ring and return to the head node

One of the questions here is where do we need to remove the ring?

We have said above that when K is 1 and 2, we need to unloop at the position of 4 and 3 nodes respectively. According to this rule, we can conclude that the unloop position is the node position after len-K steps of the end node of the previous linked list.

Here is the code implementation:

Var rotateRight = function (head, k) {/ /, sentenced to the if (head = = = null | | k = = = 0) return the head; Let cur = head,len = 1; while(cur.next){ cur = cur.next; len++; } // if k is an integer multiple of the length, no operation is required. (k %= len)) return head; // join a loop cur.next = head; Let num = len-k; while(num){ cur = cur.next; num--; } // const res = cur.next; // Unloop cur.next = null; return res; };Copy the code

If you have any questions or suggestions, please leave a comment!