1. 首页
  2. LeetCode 刷题网

LeetCode 143. 重排链表

题目描述

难度:Middle

相关话题:链表

给定一个单链表LL 0→L 1→…→L n -1→L n ,
将其重新排列后变为: L 0→L nL 1→L n -1→L 2→L n -2→…

你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

示例1:

给定链表 1->2->3->4, 重新排列为 1->4->2->3.

示例 2:

给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

思路:

两种方法:

  1. 计算出head的长度len和将要移动的节点的数量,t=Math.floor((len-1)/2),使用stack保存next会发生改变的节点。

在遍历到将要移动的节点上,执行stack.pop取出的节点作为头部,将当前节点插入到头部的next中。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {void} Do not return anything, modify head in-place instead.
 */
var reorderList = function(head) {
  if(!head)return
  let len=0
  let node=head
  while(node){
    node=node.next
    len++
  }
  let t=Math.floor((len-1)/2),k=len-t
  let stack=[],lastNode=null
  node=head
  while(node){
    if(t-->0)stack.push(node)
    if(k--<=0){
      let startNode=stack.pop(),
          secondNode=startNode.next,
          nxt=node.next
      startNode.next=node
      node.next=secondNode
      lastNode.next=nxt
      node=nxt
    }else{
      if(k===0)lastNode=node
      node=node.next
    }
  }
};
  1. 使用快慢节点找出当前head的后半段,例如[1,2,3,4,5]后半段就是[3,4,5][1,2,3,4]后半段就是[3,4]

对后半段进行反转,然后依次插入到前半段每一个节点的next中。

例如:[1,2,3,4,5,6,7],后半段是[4,5,6,7],反转后是[7,6,5,4],依次插入到[1,2,3]中,得到[1,7,2,6,3,5,4]

/**
 * @ Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {void} Do not return anything, modify head in-place instead.
 */
var reorderList = function(head) {
  if(!head)return null
  if(!head.next)return head

  let slow=head,
      fast=head.next.next
  while(fast && fast.next){
    slow=slow.next
    fast=fast.next.next
  }

  let startNode=slow, node=startNode.next
  while(node.next){
    let nxt=node.next
    node.next=nxt.next
    nxt.next=startNode.next
    startNode.next=nxt
  }
  let p1=head,
      p2=startNode.next;
  while(p1!=startNode){
    startNode.next=p2.next
    p2.next=p1.next
    p1.next=p2
    p1=p2.next
    p2=startNode.next
  }
};

看完两件小事

如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:

  1. 关注我们的 GitHub 博客,让我们成为长期关系
  2. 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
  3. 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程

JS中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。欢迎热爱技术的你一起加入交流与学习,JS中文网的使命是帮助开发者用代码改变世界

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com

标题:LeetCode 143. 重排链表

链接:https://www.javascriptc.com/4507.html

« LeetCode 144. 二叉树的前序遍历
详解git rebase,让你走上git大神之路»
Flutter 中文教程资源

相关推荐

QR code