61 Rotate List

Leetcode

Given the head of a linked list, rotate the list to the right by k places.

Example 1:

Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]

Example 2:

Input: head = [0,1,2], k = 4
Output: [2,0,1]

---

遍历链表，找到最后一个节点，求出链表长度。 k 有可能大于链表长度，所以要根据链表长度取余。再次遍历链表，找到要旋转节点的前一个节点，指向 null ，再将链表末尾指向头。时间复杂度 o(n) ，空间复杂度 o(1)

public ListNode rotateRight(ListNode head, int k) {
    if(head==null || head.next==null) return head;
    int count=1;
    ListNode t=head;
    while(t.next!=null){
        t=t.next;
        count++;
    }
    ListNode tail=t;
    k=k%count;
    if(k==0) return head;
    t=head;
    for(int i=0;i<count-k-1;++i){
        t=t.next;
    }
    ListNode ret=t.next;
    t.next=null;
    tail.next=head;
    return ret;
}