Subject to introduce

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

Example 1

Enter: head = [1.2.3.4.5], k = 2Output:4.5.1.2.3]
Copy the code

Example 2

Enter: head = [0.1.2], k = 4Output:2.0.1]
Copy the code

Tip:

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

Leetcode -61 rotation list B station video

Their thinking

Since the process of movement is cyclic, that is, when k value is greater than the length of the linked list, the process of movement will be repeated, so we should take K % n(n is the length of the linked list) to calculate the number of moves to avoid useless work

1. Define a cur pointer and iterate over the linked list to the end pointer, recording the length of the linked list n 2 at the same time. Point the last node of the linked list to the first node of the linked list, i.e. form a closed loop 3. Calculate the value of k % n 4. Taking n-k-1 steps from the beginning node, because moving the list k positions to the right, is similar to breaking the circular list from the penultimate KTH node by 5. Record that the next node of the current node is head and point the current node to NULL 6. Return head, which is the list that has been moved k positions to the right

The problem solving code

var rotateRight = function(head, k) {
    if(! head || ! head.next || k ===0) return head
    let cur = head, n = 1
    while (cur.next) {
        cur = cur.next
        n++
    }
    cur.next = head
    k %= n
    let i = n - k 
    while (--i) {
        head = head.next
    }
    cur = head
    head = cur.next
    cur.next = null
    return head
};
Copy the code

[lufei]_ ring linked list [Lufei]_ ring linked list II [Lufei]_ happy number [Lufei]_ reverse linked list II [Lufei]_ reverse linked list II [Lufei]_K group of flip linked list