T61. Rotate List【Medium】

題目

給一個鏈表，向右輪轉(zhuǎn) k 個位置（k 是非負數(shù)）。

例如：

給出 1->2->3->4->5->NULL 和 k = 2,
返回 4->5->1->2->3->NULL.

思路

主體思路：

① 求出長度 l

② 首位連通

② 右移 （l-k%l） 次 （因為 k 可能大于 l,所以要取余）

③ 把此刻的節(jié)點 next 設(shè)為 null,并返回原本的 next(因為它去了首節(jié)點)

邊界處理：

當(dāng) k = 0 或者 head 為 空時直接返回。

代碼

代碼自己寫的，能成功運行，稍作注釋

//用遞歸來完成算法
 public ListNode rotateRight(ListNode head, int k) {
        //若為0或者空則返回
        if(k==0||head==null){
            return head;
        }
        ListNode thisNode=head;
        ListNode returnNode=new ListNode(0);
        int x=1,n=1;
        //得到鏈表長度
        while(thisNode.next!=null){
            thisNode=thisNode.next;
            x++;
        }
        //連通起來
        thisNode.next=head;
        while(thisNode.next!=null){
            //找到對應(yīng)的節(jié)點，對它進行拆開重連
            if(n==(x-k%x)){
                returnNode=thisNode.next.next;
                thisNode.next.next=null;
                return returnNode;
            }
            thisNode=thisNode.next;
            n++;
        }
        return returnNode;
    }