題目
給定一個(gè)鏈表红竭，旋轉(zhuǎn)鏈表，使得每個(gè)節(jié)點(diǎn)向右移動(dòng)k個(gè)位置侣背，其中k是一個(gè)非負(fù)數(shù)
樣例
給出鏈表1->2->3->4->5->null和k=2
返回4->5->1->2->3->null
分析
關(guān)鍵是找到第一段和第二段的點(diǎn)狂窑，分割開來(lái)，最后再合在一起就行了浩淘，設(shè)置兩個(gè)指針捌朴，假設(shè)第一段的長(zhǎng)度是x,那么x+n會(huì)等于鏈表的長(zhǎng)度，所以方法自然出來(lái)了類似于尋找倒數(shù)第n個(gè)節(jié)點(diǎn)张抄。
代碼
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
private int getLength(ListNode head) {
int length = 0;
while (head != null) {
length ++;
head = head.next;
}
return length;
}
public ListNode rotateRight(ListNode head, int n) {
if (head == null) {
return null;
}
int length = getLength(head);
n = n % length;
ListNode dummy = new ListNode(0);
dummy.next = head;
head = dummy;
ListNode tail = dummy;
for (int i = 0; i < n; i++) {
head = head.next;
}
while (head.next != null) {
tail = tail.next;
head = head.next;
}
head.next = dummy.next;
dummy.next = tail.next;
tail.next = null;
return dummy.next;
}
}
