147. 对链表进行插入排序（JS实现）

素颜马尾好姑娘i 2023-03-04 08:17 27阅读 0赞

## 1 题目 ##

> 对链表进行插入排序。  
> 插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。  
> 每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。  
> 插入排序算法：  
> 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。  
> 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。  
> 重复直到所有输入数据插入完为止。  
> 示例 1：  
> 输入: 4->2->1->3  
> 输出: 1->2->3->4  
> 示例 2：  
> 输入: -1->5->3->4->0  
> 输出: -1->0->3->4->5

## 2 思路 ##

**这道题的用两个指针sortedLinkHead，sortedLinkTail指向已排序后链表的最小和最大值，当下个待排序的值位于两者之间时，才遍历已排序的列表来执行插入操作**

## 3代码 ##

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */
    /** * @param {ListNode} head * @return {ListNode} */
    var insertionSortList = function(head) { 
      if (!head || !head.next) return head;
    
      let sortedLinkHead = head;
      let sortedLinkTail = head;
      let nextEle = head.next;
      sortedLinkTail.next = null;
    
      while(nextEle) { 
        let currentEle = nextEle;
        nextEle = nextEle.next;
        if (currentEle.val <= sortedLinkHead.val) { 
          currentEle.next = sortedLinkHead;
          sortedLinkHead = currentEle;
        } else if (currentEle.val >= sortedLinkTail.val) { 
          sortedLinkTail.next = currentEle;
          currentEle.next = null;
          sortedLinkTail = currentEle;
        } else { 
          let p = sortedLinkHead;
          while(currentEle.val > p.next.val) { 
            p = p.next;
          }
          currentEle.next = p.next;
          p.next = currentEle;
        }
      }
    
      return sortedLinkHead;
    };