LeetCode_ Double pointer_ Medium_ 61. rotating linked list

1. subject

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 * 10⁹

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/rotate-list

2. Ideas

（1） Double pointer
See the comments in the following code for the detailed analysis process .

3. Code implementation （Java）

// Ideas 1———— Double pointer 
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */
class Solution {
    
    public ListNode rotateRight(ListNode head, int k) {
    
    	// Consider special circumstances 
        if (k == 0 || head == null || head.next == null) {
    
            return head;
        }
        
        // Calculate the length of the list 
        int length = 0;
        ListNode aux = head;
        while (aux != null) {
    
            aux = aux.next;
            length++;
        }
        
        //  When  k > length  when , Its rotation results are consistent with  k = k % length  equally 
        k = k % length;
        if (k == 0) {
    
        	// k % length  If it is equal to  0, shows  length  yes  k  Integer multiple , After the rotation, the result is the same as the original , So go straight back to  head
            return head;
        }
        
        /*  set up  n = length V1 -> V2 -> ... -> V(n-k-1) -> V(n-k) -> ... -> Vn -> null  Move each node of the list to the right  k  After two positions , obtain ： V(n-k) -> ... -> Vn -> V1 -> V2 -> ... -> V(n-k-1) -> null  So you just need to find the node first  V(n-k-1)、V(n-k)  as well as  Vn, Then make  V(n-k-1).next = null Vn.next = V1( namely head)  Finally back to  V(n-k)  that will do  V(n-k-1)、V(n-k)  as well as  Vn  Corresponding to  lastNode、newHead  And the last while At the end of the cycle  aux */
        aux = head;
        ListNode lastNode = head;
        int tmp = length - k;
        while (tmp > 0) {
    
            aux = aux.next;
            if (tmp != 1) {
    
                lastNode = lastNode.next;
            }
            tmp--;
        }
        lastNode.next = null;
        ListNode newHead = aux;
        while (aux.next != null) {
    
            aux = aux.next;
        }
        aux.next = head;
        return newHead;
    }
}