[Leetcode]92. Reverse Linked List II

https://leetcode.com/problems/reverse-linked-list-ii/

题意很简单,反转链表中的某一段(有可能是全部),先上我的答案:

function reverse(root, n) {
  let p,
    q,
    t = root; // we need this pointer because we should connect the reversed list with the rest the origin list
  while (root && n >= 0) {
    p = root.next;
    root.next = q;
    q = root;
    root = p;
    n--;
  }
  // right now. the t is the last node of reversed list and root is the start of unreserved list, connect them together
  t.next = root;
  return q;
}
var reverseBetween = function(head, m, n) {
  // first judge the extreme cases
  if (!head || !head.next) return head;

  // create a leader node
  let dummy = new ListNode(-1);
  dummy.next = head;
  let t = n - m; // distance between n && m
  let q = dummy;

  // we can get the q.next is the start of reversed linked list
  // why we need m > 1? because we have a dummy as the leader of head,
  // and why we need the dummy? because the reverse may be start from the index 0 :)
  while (m > 1) {
    q = q.next;
    m--;
  }
  const p = reverse(q.next, t);
  q.next = p;
  return dummy.next;
};

虽然写了注释,但是还是解释一下步骤:

  1. 判断特殊情况:没有head或者只有head,直接返回headleetcode.png
  2. 声明一个辅助节点dummy作为head的头节点,为什么需要dummy?因为可能整个list都要反转
  3. t是要反转的节点数量,q作为另一个dummy辅助节点,因为dummy我们要作为固定的node,所以需要另外一个可迭代的q节点leetcode .png
  4. 通过while(m>1)得到q节点的最新值,这时候的q.next节点就是要开始反转的list的开始节点leetcode.png
  5. 写一个反转链表的函数,相信各位对于这个很得心应手了。不过这里有两个trick:leetcode.png
  • 除了把第4步的q.next做为开始节点,还需要第3步的t,因为我们不可无限的进行链表反转,t就是我们的一个限制
  • 当我们把m~n之间的节点反转之后,我们要把nodes>n的剩余链表拼接回反转链表之后,这样我们才可以保持剩余链表的原始性,这里怎么做呢?我们只需要在一开始把root节点保存起来(t),因为我们知道,当一个以root为开始节点的链表反转之后,最开始的节点root就变成了最后的节点,而在现在的这个题意中,循环终止时的节点(root)就是剩余链表的开始节点,我们只需要把t.next = root就完成了最后的拼接leetcode.png
  1. 得到了反转之后的p节点。现在只需要把第4步的q.next = p,就完成了整个原始list的拼接
  2. 返回dummy.next即可

有问题欢迎邮件或者telegram联系我