Rotate List(0061/Medium)链表旋转

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:

Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

解法1(java)

1. 计算链表长度
2. 从原链表最后一个节点走len-k步到新旋转后链表的最后一个节点
3. 当k>len的时候，旋转实际长度为k%len

public ListNode rotateRight(ListNode head, int k) {
    //deal with corner case
    if(head==null||head.next==null)
        return head;

    int len=0;

    //store head in temp head
    ListNode tempHead = head;

    //scan from begin to end to find out the length
    while(head!=null && head.next!=null){
        len++;
        head=head.next;
    }

    //length is 1 smaller than actual length here, so add one
    len++;

    //when k is larger than length, we need to rotate from k%length
    k=k%(len);
    if(k==0)
      return head;

   //connect the last node with temphead
    head.next=tempHead;

    for(int i=0; i<(len-k); i++){
        head =head.next;
    }
    ListNode newHead = head.next;
    head.next=null;

    return newHead;
}

解法2(java)

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

//split list at kth from end
// reverse(0,length-k-1)
// reverse(length-k,n-1)
// reverse(0,n-1)
public ListNode rotateRight(ListNode head, int k) {
    ListNode curr=head;
    if(head==null||head.next==null)
        return head;

    int nr=0;
    while(curr!=null){
        nr++;
        curr=curr.next;
    }
    k=k%nr;
    if(k==0)
        return head;

    ListNode p=head,q=head;
    int x=0;
    while(x!=k){
        q=q.next;
        x++;
    }
    while(q.next!=null){
        p=p.next;
        q=q.next;
    }

    //p.next链表旋转后的头结点
    ListNode save=p.next;

    ListNode a=reverse(head,p.next);
    ListNode end= reverse(save,null);
    head.next=end;

    return reverse(a,null);
}

public ListNode reverse(ListNode head,ListNode to){
    ListNode curr=head;
    ListNode prev=null;
    while(curr!=to){
        ListNode next=curr.next;
        curr.next=prev;
        prev=curr;
        curr=next;
    }
    head=prev;
    return head;
}