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

The title

61. Rotate the list to give you the head of the list. Rotate the list to 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] example 2: input: head = [0,1,2], k = 4 output: [2,0,1] hint: The number of nodes in the linked list is in the range [0, 500] -100 <= node. val <= 100 0 <= k <= 2 * 109Copy the code

parsing

The linked list problem is basically the easiest problem in leetCode, so let’s talk about some of the ways to solve the linked list problem.

As far as this problem is concerned, we know that the simplest way to solve it is:

  • Take the k out of the back and connect it to the front

However, it is impossible to know the unknown list length in advance, and the simplest is:

  • Hard to: we no matter three seven twenty-one, the first length out for length, and then take the former length-k, backward connect

This is the easiest way, and I won’t repeat it here. Of course, we can also use a trick of linked list problems:

  • Double pointer (also called fast or slow pointer)

A fast pointer runs in front and a slow pointer runs behind. The interval between the two is M or the interval between each step is N. Then when the fast pointer arrives at the end, just our slow pointer goes length-m or Length /N.

Because length may be less than k, we also need to do special treatment for length less than k, as follows:

public static ListNode rotateRightDoublePtr(ListNode head, int k){ if(head == null || head.next == null || k == 0) return head; ListNode dummy = new ListNode(0); dummy.next = head; ListNode after,tur = dummy; int length = 0,idx = 0; While (tur. Next! =null && length ! = k){ tur = tur.next; length++; idx++; If (tur. Next ==null){k = k%length; if(k == 0) return head; tur = dummy; idx = 0; } // Note the idx, while(tur. Next! =null && idx ! = k){ tur = tur.next; idx++; } // add a pointer after = dummy; while(tur.next! =null){ tur = tur.next; after = after.next; } // dummy. Next = after. Next; after.next = null; tur.next = head; return dummy.next; }Copy the code

Execution time: 0 ms, beating 100.00% of users in all Java commits

Memory consumption: 37.8 MB, beating 48.34% of all Java commits

Here’s another interesting idea:

  • Circular linked list

    Turn our list into a circle, then take k steps from head and break, and pull out the same result as the answer.

public static ListNode rotateRightCircle(ListNode head, int k) { if (k == 0 || head == null || head.next == null) { return head; } int n = 1; ListNode iter = head; while (iter.next ! = null) { iter = iter.next; n++; } int add = n - k % n; if (add == n) { return head; } iter.next = head; while (add-- > 0) { iter = iter.next; } ListNode ret = iter.next; iter.next = null; return ret; }Copy the code

\