写点什么

LeetCode 题解:61. 旋转链表,闭合为环,JavaScript,详细注释

用户头像
Lee Chen
关注
发布于: 1 小时前
LeetCode题解:61. 旋转链表,闭合为环,JavaScript,详细注释

原题链接:61. 旋转链表


解题思路:


  1. 输入:head = [1,2,3,4,5], k = 2

  2. 如果将链表连接成环,会变成这样的样子:[1,2,3,4,5,1,2,3,4,5, ...]

  3. 此时我们只要将3 → 4的连接打断,即可得到结果:[4,5,1,2,3]

  4. 由于开始时,我们只知道链表的头节点,因此要把问题按步骤解决:

  5. 用一个指针node,从链表的头节点移动到尾结点,统计链表长度。

  6. 将链表尾结点与头结点连接。

  7. 用一个指针breakNode,将其移动到需要打断的位置,breakNode的下一个节点即为新链表的头结点。

  8. 将链表打断,并返回新链表的头节点。


/** * @param {ListNode} head * @param {number} k * @return {ListNode} */var rotateRight = function (head, k) {  // 以下条件无需旋转,直接返回即可  if (    // 链表为空    !head ||    // 链表只有一个节点    !head.next ||    // 旋转数量为0    k === 0  ) {    return head;  }  // 使用一个指针,统计链表长度  let node = head;  // 统计节点数量,指针初始指向头结点,因此初始值为1  let length = 1;
// 不断移动指针,但它停在尾结点时,完成链表长度的统计 while (node.next) { node = node.next; length++; } let rotate = k % length; // 链表旋转节点数量,k可能大于链表长度,因此需要取余
// 如果rotate为0,无需旋转,直接返回即可 if (rotate === 0) { return head; }
// 将尾结点与头结点连接,让链表形成环 node.next = head; let breakNode = head; // 使用指针,最终会指向断点位置 let breakPoint = length - rotate - 1; // 将指针移动到断点位置所需次数
// 将指针移动到断点位置 while (--breakPoint >= 0) { breakNode = breakNode.next; }
// 链表的新头结点,就在断点位置的下一个节点 const newHead = breakNode.next; // 将链表的环打断 breakNode.next = null;
// 返回新链表 return newHead;};
复制代码


发布于: 1 小时前阅读数: 2
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:61. 旋转链表,闭合为环,JavaScript,详细注释