旋转链表
原题链接：https://leetcode-cn.com/problems/rotate-list/submissions/
一、问题描述
给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
示例 1：
输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]
示例 2：
输入：head = [0,1,2], k = 4
输出：[2,0,1]
提示：
链表中节点的数目在范围 [0, 500] 内
-100 <= Node.val <= 100
0 <= k <= 2 * 109
二、问题分析
显然如果每次移动一个位置循环k次，可以实现这个代码，但是时间复杂度就是n^n，几乎不能用的一个代码。
如果把最后一个元素和第一个元素链接，然后在这个循环链表中找一个位置把链表断开，这样就能轻松完成旋转，首先是k，如果k大于链表长度，那么其实只需要移动k%lengrh，次就行了。然后分析断点，对于最后一个元素来说，k的值就是该元素在新链表中应该出现的位置，那么就可以从后往前数k个元素然后断开就行。但是从后往前不方便，从后往前数k个元素也就是从前往后数length-k个元素，所以只需要从前往后数length-k个元素然后断开即可。
三、代码
1 /** 2 * 链表结构 3 * Definition for singly-linked list. 4 * public class ListNode { 5 * int val; 6 * ListNode next; 7 * ListNode() {} 8 * ListNode(int val) { this.val = val; } 9 * ListNode(int val, ListNode next) { this.val = val; this.next = next; } 10 * } 11 */ 12 class Solution { 13 public ListNode rotateRight(ListNode head, int k) { 14 if(head == null||k==0){ 15 return head; 16 } 17 ListNode nhead = new ListNode(); 18 nhead.next = head; 19 ListNode i = nhead; 20 int length = 0; 21 while(i.next != null){//循环找出最后一个结点，并记录链表长度 22 length++; 23 i = i.next; 24 } 25 k = k%length; 26 if(k==0){ 27 return head; 28 } 29 k=length-k;//要从后往前数k个结点断开，所以就是从前往后数length-k个结点 30 i.next = nhead.next;//把链表头尾相连 31 i=nhead;//重定位i，用于后续操作 32 while(k!=0){ 33 i=i.next; 34 k--; 35 } 36 nhead.next = i.next; 37 i.next = null; 38 39 return nhead.next; 40 } 41 }
原文：https://www.cnblogs.com/zyq79434/p/15041580.html