1、題目鏈接
https://leetcode.com/problems/rotate-list/
2、解題思路
這道題的意思是說給你一個鏈表head,然后再給你一個非負整數(shù)k,要求讓你將這個鏈表的倒數(shù)k個元素旋轉(zhuǎn)放到表頭位置掀潮,就好比hea=1->2->3->4->5->NULL,k=2琼富,旋轉(zhuǎn)之后head=4->5->1->2->3->NULL仪吧;我剛開始的想法是先將鏈表截斷,然后再拼接起來鞠眉,發(fā)現(xiàn)這樣比較費事薯鼠,然后我想著是不是可以把這個鏈表弄成一個環(huán)形的,直接把表尾鏈接到表頭部械蹋,然后在計算截斷的位置就好了出皇,截斷的話直接將listNode.next置空即可。
3朝蜘、代碼
- Java
public ListNode rotateRight(ListNode head, int k) {
if (null == head || null == head.next || k == 0) {
return head;
}
int length = 0;
ListNode listNode = head;
while (null != listNode) {
length++;
listNode = listNode.next;
}
listNode = head;
while (null != listNode.next) {
listNode = listNode.next;
}
listNode.next = head;
int cnt = length - k % length; //注意可能會比鏈表長度大
ListNode listNode1 = listNode;
while (cnt > 0) {
listNode1 = listNode1.next;
cnt--;
}
ListNode listNode2 = listNode1.next;
listNode1.next = null;
return listNode2;
}