2019-10-22

文章目錄：

1. 題目要求
2. 解題思路
3. 具體實現(xiàn)
4. 改進(jìn)之路
5. 總結(jié)

1. 題目要求

給定一個鏈表，旋轉(zhuǎn)鏈表，將鏈表每個節(jié)點(diǎn)向右移動 k 個位置，其中 k 是非負(fù)數(shù)旱捧。

示例 1:
輸入: 1->2->3->4->5->NULL, k = 2
輸出: 4->5->1->2->3->NULL
解釋:
向右旋轉(zhuǎn) 1 步: 5->1->2->3->4->NULL
向右旋轉(zhuǎn) 2 步: 4->5->1->2->3->NULL

示例 2:
輸入: 0->1->2->NULL, k = 4
輸出: 2->0->1->NULL
解釋:
向右旋轉(zhuǎn) 1 步: 2->0->1->NULL
向右旋轉(zhuǎn) 2 步: 1->2->0->NULL
向右旋轉(zhuǎn) 3 步: 0->1->2->NULL
向右旋轉(zhuǎn) 4 步: 2->0->1->NULL

示例 3:
輸入: 0->1->2->NULL, k = 3
輸出: 0->1->2->NULL
解釋:
向右旋轉(zhuǎn) 1 步: 2->0->1->NULL
向右旋轉(zhuǎn) 2 步: 1->2->0->NULL
向右旋轉(zhuǎn) 3 步: 0->1->2->NULL

來源：力扣LeetCode
本文僅做個人刷題記錄，不做任何商業(yè)用途踩麦。

2. 解題思路

根據(jù)測試用例枚赡，可以知道：
a. 鏈表反轉(zhuǎn)次數(shù) 和 k 與鏈表長度之間的關(guān)系 有關(guān)聯(lián)；
b. 求鏈表長度 length谓谦；length == 0 或 length == k贫橙，鏈表不變；
c. 將鏈表每個節(jié)點(diǎn)向右移動 k 個位置反粥，即 第 i 位置的元素 移到 第 i+k 位置 卢肃，考慮到單鏈表的移動問題，將鏈表頭尾相連轉(zhuǎn)換成循環(huán)鏈表才顿，
old_tail.next = old_head;
d. 找到新的表頭（即 n-k ）和表尾( n-n%k-1 )莫湘， new_head = new_tail.next;
e.斷開循環(huán)鏈表，恢復(fù)單鏈表郑气，new_tail.next = null.

3. 具體實現(xiàn)

 public ListNode rotateRight(ListNode head, int k) {
    //界值判斷   
    if(head==null||k==0){
        return head;
    }
    //新建一個鏈表
    ListNode res=head;
    ListNode tail=null;
    int length=1;
    //獲取鏈表長度幅垮，新鏈表賦值
    while(res.next!=null)
    {
        res=res.next;
        length++;
    }
    //得到循環(huán)的次數(shù)
    int loop=length-(k%length);
    //指向尾結(jié)點(diǎn)
    tail=res;
    //連接成循環(huán)鏈表
    res.next=head;
    res=head;
       
    for(int i=0;i<loop;i++){
        res=res.next;
        tail=tail.next;
    }
    //斷開
    tail.next=null;
    return res;
}

4. 改進(jìn)之路

a. 先連接頭和尾，形成環(huán)尾组；
b. 找到新的尾結(jié)點(diǎn)和頭結(jié)點(diǎn)忙芒；
c. 斷開閉環(huán)示弓。

 public ListNode rotateRight(ListNode head, int k) {
    // 界值判斷
    if (head == null) return null;
    if (head.next == null) return head;

    // 連接頭和尾，形成閉環(huán)
    ListNode old_tail = head;
    int n;
    for(n = 1; old_tail.next != null; n++){
        old_tail = old_tail.next;
    }
    // 界值判斷
    if(n == k) return head;
    old_tail.next = head;

    // 新的尾結(jié)點(diǎn) : 第 (n - k % n - 1)個結(jié)點(diǎn)
    // 新的頭結(jié)點(diǎn) : 第 (n - k % n)個結(jié)點(diǎn)
    ListNode new_tail = head;
    for (int i = 0; i < n - k % n - 1; i++){
        new_tail = new_tail.next;
    }
    ListNode new_head = new_tail.next;

    //斷開
    new_tail.next = null;

    return new_head;
  }

5. 總結(jié)

先想清楚測試用例呵萨，確定邊界和邏輯奏属，然后根據(jù)測試用例寫代碼。文中內(nèi)容參考了 leetcode 給出的標(biāo)準(zhǔn)答案甘桑。