问题描述
https://leetcode.com/problems/rotate-list/
解决思路
用双指针fast和slow指向head，先用fast算出listNode的长度len，然后先移动fast到k%len的位置，然后将slow和fast同时向后移动k%len。最后此时slow指向的应该是新listNode的尾节点（除去null先不谈），slow.next应该是新节点的头节点。通过fast.next将原数组首尾连接，形成新的listNode，将slow.next设为head，最后将slow.next指向null使中间断开，形成旋转后的新的listNode
代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode rotateRight(ListNode head, int k) {
//corner case
if(head == null) return head;
//define two pointer
ListNode fast = head;
ListNode slow = head;
int len = 0;
//use fast pointer to count the length of the listNode
while(fast != null){
len++;
fast = fast.next;
}
fast = head;
for(int i = 0; i < k % len; i++){
fast = fast.next;
}
while(fast.next != null){
slow = slow.next;
fast = fast.next;
}
fast.next = head;
head = slow.next;
slow.next = null;
return head;
}
}
复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(1)
