Heading

61.旋转链表 (opens new window)

Tags: algorithms linked-list two-pointers

Langs: c cpp csharp golang java javascript kotlin php python python3 racket ruby rust scala swift typescript

• algorithms
• Medium (40.53%)
• Likes: 395
• Dislikes: -
• Total Accepted: 107.7K
• Total Submissions: 265.3K
• Testcase Example: '[1,2,3,4,5]\n2'

给定一个链表，旋转链表，将链表每个节点向右移动 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

/*
 * @lc app=leetcode.cn id=61 lang=javascript
 *
 * [61] 旋转链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
// var rotateRight = function (head, k) {
//     if (!head) return null;
//     if (!head.next) return head;

//     //连成一个环
//     let p = head,length = 1;
//     while (p.next) {
//         p = p.next
//         length++
//     }
//     let q = p;
//     p = head;
//     q.next = p;
//     //遍历step次，断开环
//     const step = length-k%length;
//     for (let i = 0; i < step; i++) {
//         q = p;
//         p = p.next;
//     }
//     q.next = null;
//     return p;
// };
var rotateRight = function (head, k) {
    if (!head) return null;
    let p = head, length = 0, q;
    //计算length,q保存尾结点
    while (p) {
        q = p;
        p = p.next;
        length++;
    }
    if(k%length === 0) return head;
    //找到头结点的前一个节点
    let preHeadIdx = length - k % length - 1;
    p = head;
    while (preHeadIdx-- > 0) {
        p = p.next;
    }
    //断开并用尾结点连接head
    const newHead = p.next;
    p.next = null;
    q.next = head;
    return newHead;

};
// @lc code=end


// @after-stub-for-debug-begin
module.exports = rotateRight;
// @after-stub-for-debug-end