力扣面试150题--旋转链表

Day 38

题目描述

思路

/*** 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) {if(head==null){//处理空链表return null;}ListNode fakehead=new ListNode();fakehead.next=head;//空头结点ListNode z=fakehead;ListNode x=head;int len=1;while(x.next!=null){//找到链表长度x=x.next;len++;}k=k%len;//防止k大于lenif(k==0){//说明k被除尽了 不需要处理return head;}ListNode y=head;x=head;int i=1;while(i!=k){y=y.next;i++;}while(y.next!=null){z=z.next;x=x.next;y=y.next;}//以上代码复用了找到倒数第k个元素，z为倒数第k+1的元素//x为倒数第k个元素z.next=null;//此时旋转，k为最后一个，指向nully.next=fakehead.next;//结尾变为空头指针的后一个fakehead.next=x;//空头指针指向倒数第k个元素return fakehead.next;//建议画图理解}
}