旋转链表
题目描述：给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
示例说明请见LeetCode官网。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rotate-list/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解法一：双指针法
首先，如果head为null或者head只有一个节点，直接返回head；
遍历链表head得到链表的长度为length，根据
k % length算得toJump，toJump为实际需要多少位挪到链表前面，如果toJump为0，说明旋转后不需要挪动，直接返回head，如果toJump大于0，则初始化2个节点first和last分别指向头结点，然后利用双指针法，得到需要挪的最后几位，具体处理过程如下：
- 首先将last移动到链表的第toJump位；
- 然后同时移动first和last节点，直到last的next不为空为止。
最后移动到last的next为空，此时last即为原链表的最后一个节点，first的next节点为新的头结点，此时，初始化newHead为first的next节点，然后将first的next置空，first为新链表的最后一个节点，然后将last指向原链表的头结点head，最后返回newHead即为旋转后的链表。
public class LeetCode_061 {
public static ListNode rotateRight(ListNode head, int k) {
if (head == null || head.next == null) {
return head;
}
ListNode cur = head;
// 链表的长度
int length = 0;
while (cur != null) {
length++;
cur = cur.next;
}
// 需要将倒数 toJump 位挪到 head 节点前面
int toJump = k % length;
if (toJump == 0) {
return head;
}
ListNode first = head, last = head;
while (toJump > 0) {
last = last.next;
toJump--;
}
while (last.next != null) {
first = first.next;
last = last.next;
}
ListNode newHead = first.next;
first.next = null;
last.next = head;
return newHead;
}
public static void main(String[] args) {
ListNode head = new ListNode(0);
head.next = new ListNode(1);
head.next.next = new ListNode(2);
ListNode listNode = rotateRight(head, 4);
while (listNode != null) {
System.out.print(listNode.val + " ");
listNode = listNode.next;
}
}
}
【每日寄语】 只要你今天再多努力一下，那个未来可以像星星一样闪闪发光的人就是你呀！
