旋轉(zhuǎn)鏈表

題目描述：給你一個(gè)鏈表的頭節(jié)點(diǎn) head ，旋轉(zhuǎn)鏈表，將鏈表每個(gè)節(jié)點(diǎn)向右移動(dòng) k 個(gè)位置。

示例說明請(qǐng)見LeetCode官網(wǎng)。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/rotate-list/
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

解法一：雙指針法

• 首先，如果head為null或者h(yuǎn)ead只有一個(gè)節(jié)點(diǎn)，直接返回head；

• 遍歷鏈表head得到鏈表的長度為length，根據(jù)k % length算得toJump，toJump為實(shí)際需要多少位挪到鏈表前面，如果toJump為0，說明旋轉(zhuǎn)后不需要挪動(dòng)，直接返回head，如果toJump大于0，則初始化2個(gè)節(jié)點(diǎn)first和last分別指向頭結(jié)點(diǎn)，然后利用雙指針法，得到需要挪的最后幾位，具體處理過程如下：

  • 首先將last移動(dòng)到鏈表的第toJump位；
  • 然后同時(shí)移動(dòng)first和last節(jié)點(diǎn)，直到last的next不為空為止。

• 最后移動(dòng)到last的next為空，此時(shí)last即為原鏈表的最后一個(gè)節(jié)點(diǎn)，first的next節(jié)點(diǎn)為新的頭結(jié)點(diǎn)，此時(shí)，初始化newHead為first的next節(jié)點(diǎn)，然后將first的next置空，first為新鏈表的最后一個(gè)節(jié)點(diǎn)，然后將last指向原鏈表的頭結(jié)點(diǎn)head，最后返回newHead即為旋轉(zhuǎn)后的鏈表。

public class LeetCode_061 {
    public static ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode cur = head;
        // 鏈表的長度
        int length = 0;
        while (cur != null) {
            length++;
            cur = cur.next;
        }
        // 需要將倒數(shù) toJump 位挪到 head 節(jié)點(diǎn)前面
        int toJump = k % length;
        if (toJump == 0) {
            return head;
        }
        ListNode first = head, last = head;
        while (toJump > 0) {
            last = last.next;
            toJump--;
        }
        while (last.next != null) {
            first = first.next;
            last = last.next;
        }
        ListNode newHead = first.next;
        first.next = null;
        last.next = head;
        return newHead;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(0);
        head.next = new ListNode(1);
        head.next.next = new ListNode(2);

        ListNode listNode = rotateRight(head, 4);
        while (listNode != null) {
            System.out.print(listNode.val + " ");
            listNode = listNode.next;
        }
    }
}

【每日寄語】 只要你今天再多努力一下，那個(gè)未來可以像星星一樣閃閃發(fā)光的人就是你呀！