NC70.单链表排序

TIP

标签：链表、排序

描述

给定一个无序单链表，实现单链表的排序（按照升序排列）

示例：

输入：[1,3,2,4,5]
输出: {1,2,3,4,5}

算法思路

值排序，不是真正做到链表排序，直接遍历整个链表，用一个数组存储所有的val，然后进行排序，最后将排序完的值赋给链表。

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
 * 
 * @param head ListNode类 the head node
 * @return ListNode类
 */
function sortInList( head ) {
  // write code here
  // 值排序不是真正的排序，需要遍历整个链表，用一个数组存储所有的val
  // 然后进行排序 最后将排序完的值赋值给链表
  if(head == null || head.next ==null) {
    // 这里注意返回值是 ListNode 
    return head // 不需要排序
  }
  // 如何提高项目的复杂度
  let arr = []
  let temp = head
  
  while(temp !== null) {
    arr.push(temp.val)
    temp = temp.next
  }
  
  arr.sort((a,b)=>{
    return a - b // 升序排列
  })
  let tmp = head
  while(tmp !== null) {
    tmp.val = arr.shift()
    tmp = tmp.next
  }
  return head
}
module.exports = {
  sortInList : sortInList
};