61. 旋转链表
给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数
解题思路1-迭代法
迭代操作：每次都使链表的尾节点成为新的头节点
解题关键：当链表的旋转次数等于链表长度时，链表会还原。因此需要取k整除链表长度的余数作为迭代次数。否则此种解法会超出时间限制。
代码实现
/**
* 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;
}
//旋转次数=链表长度时，链表会还原
k = k % getLength(head);
while(k != 0){
ListNode temp = head;
//找到倒数第二个节点
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)
