旋转链表-双指针思想-LeetCode61

题目要求：给定链表的头结点，旋转链表，将链表每个节点向右移动K个位置。
示例：
输入：head = [1,2,3,4,5], k=2
输出：[4,5,1,2,3]

双指针思想：
先用双指针策略找到倒数K的位置，也就是(1,2,3)和4,5)两个序列，之后再将两个链表拼接成(4,5,1,2,3}就行了。
具体思路是:
因为k有可能大于链表长度，所以首先获取一下链表长度len，如果然后k=k % len，如果k == 0，则不用旋转，直接返回头结点。否则:
1、快指针先走k步
2、慢指针和快指针一起走
3、快指针走到链表尾部时，慢指针所在位置刚好是要断开的地方。把快指针指向的节点连到原链表头部，慢指针指向的节点断开和下一节点的联系
4、返回结束时慢指针指向节点的下一节点

import java.util.*;public class RotateRight_旋转数组 {public static void main(String[] args) {//int[] a = {1, 2, 3, 4, 5};ArrayList<Integer> lst = new ArrayList<>();//输入Scanner scanner = new Scanner(System.in);String s = scanner.nextLine();Scanner input = new Scanner(s);while(input.hasNextInt()){lst.add(input.nextInt());}Integer[] a = lst.toArray(new Integer[lst.size()]);ListNode nodeA = initLinkedList(a); //数组初始化为链表ListNode nodeB = initLinkedList2(lst); //集合初始化为链表ListNode node = rotateRight(nodeB, 2);  //开始旋转System.out.println(toString(node));}//定义链表节点static class ListNode{public int val;public ListNode next;ListNode(int x){val = x;next = null;}}//数组初始化链表public static ListNode initLinkedList(Integer[] a){ListNode head = null, cur = null;for (int i = 0; i < a.length; i++){ListNode newNode = new ListNode(a[i]);if (i==0){head = newNode;cur = newNode;}else{cur.next = newNode;cur = cur.next;}}return head;}//集合初始化链表public static ListNode initLinkedList2(ArrayList a){ListNode head = null, cur = null;for (int i = 0; i < a.size(); i++){ListNode newNode = new ListNode((Integer) a.get(i));if (i==0){head = newNode;cur = newNode;}else{cur.next = newNode;cur = cur.next;}}return head;}//开始旋转public static ListNode rotateRight(ListNode head, int k) {if (head == null || k == 0) {return head;}ListNode temp = head;ListNode fast = head;ListNode slow = head;int len = 0;//链表的长度while (head != null) {head = head.next;len++;}//如果能整除，则直接返回该链表if (k % len == 0) {return temp;}while ((k % len) > 0) {k--;fast = fast.next;}while (fast.next != null) {fast = fast.next;slow = slow.next;}ListNode res = slow.next;slow.next = null;fast.next = temp;return res;}//输出链表public static String toString(ListNode head) {ListNode current = head;//StringBuilder可以用来拼接字符串StringBuilder sb = new StringBuilder();while(current !=null){sb.append(current.val).append("\t");current = current.next;}return sb.toString();}}