LeetCode-61-旋转链表

链表 双指针

原题地址：旋转链表

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL

示例 2:

输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL

准备工作

定义链表节点：

function ListNode(val) {
    this.val = val;
    this.next = null;
}

数组转链表，方便测试数据的输入：

function arrayT[两两交换链表中的节点](https://blog.lihaiping.cn/archives/swap-nodes-in-pairs)oList(array) {
    let node = null;
    for (let i = array.length - 1; i >= 0; i --) {
        let newNode = new ListNode(array[i]);
        newNode.next = node;
        node = newNode;
    }
    return node;
}

链表转字符串，方便测试结果的显示：

function listToString(node) {
    return node ? `${node.val}${node.next ? ` -> ${listToString(node.next)}` : '' }` : null;
}

遍历

先遍历一次，确定链表的长度并将尾结点与头结点连接，形成循环链表。然后根据右移的长度，确定新链表应该断裂的位置即可。

具体的实现代码如下：

/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
const rotateRight1 = function(head, k) {
    // 空链表旋转得到的也是空链表
    if (head == null) {
        return null;
    }
    // 额外的头指针方便处理
    let preHead = new ListNode(null);
    preHead.next = head;
    // 记录链表的长度
    let count = 0;
    while (head.next) {
        count ++;
        head = head.next;
    }
    count ++;
    // 将链表的尾部与头部连起来
    head.next = preHead.next;
    // 旋转count次会得到原来的链表，所以需要取模
    k = k % count;
    // 向右移动k次后，count-k处会断开，形成新的头节点和尾节点
    for (let i = 0; i < count - k; i ++) {
        head  = head.next;
    }
    preHead.next = head.next;
    head.next = null;
    // 返回新的头节点
    return preHead.next;
};

测试：

let start = new Date();
const test = rotateRight1;
console.log(listToString(test(arrayToList([1,2,3,4,5]),2))); // 4 -> 5 -> 1 -> 2 -> 3
console.log(listToString(test(arrayToList([0,1,2]),4))); // 2 -> 0 -> 1
console.log(new Date().getTime() - start.getTime()); // 7

时间复杂度： 确定链表长度需要一次遍历，确定新的链表头尾节点需要一次遍历，总时间复杂度为$O(2N)=O(N)$
空间复杂度： 原地操作，空间复杂度为$O(1)$

本文由 李海平 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Aug 17,2019