This is the 28th day of my participation in the August Text Challenge.More challenges in August

preface

The rotation list of question 61 is as follows:

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

A, thinking

Put k elements at the end of the list into the head of the list

I started with a fast or slow pointer, but I had trouble handling k > head.len. For example, head = [0,1,2] in example 2, k = 4 is k > head.len.

Therefore, I changed the way of thinking, and the implementation steps can be roughly divided into the following two steps:

  1. Point the end of the list to the head to form a circle, with a temporary pointerheadTempPoint to the end of the list
  2. And find where the ring broke off
  3. Returns the new head nodenewHead

Graphic algorithm

Here, head = [1, 2, 3, 4, 5] and k = 12 are used as examples

  1. Start by pointing the tail towards the head to form a circle

  1. Find where the ring broke

We know that the temporary pointer headTemp points to the last node of the list, 5, when forming a circle

We know that when k = 1, the ring should break at 4 -> 5, and the number of steps required from the temporary pointer is P = 4, as shown below:

When k = 2, the ring should break at 3 -> 4, and the number of steps required from the temporary pointer is P = 3, as shown below:

We find that the position of the break is from back to front. When k == head. Len, that is, k == 5, it is equivalent to a cycle. The ring should break at the point where the last node of the list points to the first node, i.e., 5 -> 1. As shown below:

To sum up, the break position is: from the temporary pointer headTemp, the break can take p = len-k % len step (to take the minimum number of steps, so the mod).

Therefore, k = 12 is disconnected by taking p = 5-12% and 5 = 3 steps from the temporary pointer, as shown in the figure below:

Second, the implementation

The implementation code

Head == null; head == null;

    /** ** list to ring */
    public ListNode rotateRight(ListNode head, int k) {
        // Special circumstances
        if (head == null) {
            return null;
        }
        // Make it a circle first
        int len = 0;
        ListNode headTemp = head;
        while (true) {
            len++;
            if (headTemp.next == null) {
                headTemp.next = head;
                break;
            }
            headTemp = headTemp.next;
        }
        // Where do I disconnect
        int p = len - k % len;
        while (p > 0) {
            headTemp = headTemp.next;
            p--;
        }
        ListNode newHead = headTemp.next;
        headTemp.next = null;
        return newHead;
    }
Copy the code

The test code

    public static void main(String[] args) {
        ListNode listNode = new ListNode(1.new ListNode(2.new ListNode
        (3.new ListNode(4.new ListNode(5)))));
        new Number61().rotateRight(listNode, 12);
    }
Copy the code

The results of

Third, summary

Thank you to see the end, very honored to help you ~♥

If you think my writing is good, you might as well give me a thumbs-up! If you have any questions, please see the comments section