61. 旋轉(zhuǎn)鏈表
給定一個鏈表举反，旋轉(zhuǎn)鏈表，將鏈表每個節(jié)點向右移動 k 個位置扒吁，其中 k 是非負數(shù)
解題思路1-迭代法
迭代操作：每次都使鏈表的尾節(jié)點成為新的頭節(jié)點
解題關鍵：當鏈表的旋轉(zhuǎn)次數(shù)等于鏈表長度時火鼻，鏈表會還原。因此需要取k整除鏈表長度的余數(shù)作為迭代次數(shù)雕崩。否則此種解法會超出時間限制凝危。
代碼實現(xiàn)
/**
* 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 || head.next == null){
return head;
}
//旋轉(zhuǎn)次數(shù)=鏈表長度時，鏈表會還原
k = k % getLength(head);
while(k != 0){
ListNode temp = head;
//找到倒數(shù)第二個節(jié)點
while(temp.next.next != null){
temp = temp.next;
}
ListNode tail = temp.next;
tail.next = head;
temp.next = null;
head = tail;
k = k-1;
}
return head;
}
public int getLength(ListNode head){
int len = 0;
while(head != null){
len++;
head = head.next;
}
return len;
}
}
時間復雜度：最壞情況O(n^2)晨逝，最好情況O(n)
空間復雜度：最壞情況O(n)蛾默，最好情況O(1)
