LeetCode 143. 重排链表

题目描述

难度：Middle

相关话题：链表

给定一个单链表L ：L 0→L 1→…→L n -1→L n ，
将其重新排列后变为： L 0→L n →L 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.

思路：

两种方法：

计算出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
    }
  }
};

使用快慢节点找出当前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
  }
};