首页 > 代码库 > 第22题 Rotate List
第22题 Rotate List
Given a list, rotate the list to the right by k places, where k is non-negative.
For example:
Given 1->2->3->4->5->NULL
and k = 2
,
return 4->5->1->2->3->NULL
.
Solution:
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode rotateRight(ListNode head, int n) { if(head==null||head.next==null || n==0) return head; ListNode fakeHead = new ListNode(0); fakeHead.next=head; int length=0; ListNode start=fakeHead, end=fakeHead; for(int i=0; i<n; i++){ if(end.next==null) break; end=end.next; length++; } if(end.next==null){ //when n>=length //int startPos = (length-n)%length+length; //Or: int startPos=n%length; if(startPos==0) return fakeHead.next; startPos=length-startPos; for(int i=0; i<startPos; i++){ start=start.next; } } else{ while(end.next!=null){ start=start.next; end=end.next; } } //reorder list end.next=fakeHead.next; fakeHead.next=start.next; start.next=null; return fakeHead.next; } }Note:假设end后移n次后end.next还不是null,说明list的长度>n。则将start和end总体后移。
否则,说明list的长度<=n,这时候须要找到rotate的实际次数。对于一个长为length的list,若rotate的次数为length,则结果为原list。所以rotate的实际次数是n%length,若结果为0,则直接返回原list;否则,须要找到对应的start点,即改动list的起始点。
注意代码中
int startPos = (length-n)%length+length;事实上和
int startPos=n%length; startPos=length-startPos;一个效果(startPos不为0时)。可是后者比較好理解。
另外一个负数对一个正数取模,计算例如以下:
result=m%n, where m<=0, n>0
Assume m=xn+result, where x<=0, result<0 and -result<n.
比方(-5)%3。 -5=3*(-1)+(-2)。所以(-5)%3=-2。
第22题 Rotate List
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。