leetcode 147 对链表进行插入排序

leetcode 第147题目 对链表进行插入排序

题目要求

使用插入排序对链表进行排序操作并且返回排序后的链表的头节点

思路

首先我们可以生成一个链表，这个链表刚生成的时候头指针指向**头节点**，之后我们在头节点后续进行插入操作即可，我们每次进行插入都需要找到实际要插入的位置，这个也好做，通过一个while循环即可。

先说明定义的几个指针

• preHead指针：这个就是我们新的链表的头结点
• preNewHead指针：我们保存了一份头结点，因为在while循环中我们需要移动头指针，找到一个节点他应该插入的正确位置，所以我们在插入之后需要将preHead移动回头指针，我们每次寻找节点的正确位置都是从新链表的头开始往后遍历
• curry指针，我们需要生成一个新的节点插入到新链表

图解

测试用例：[4,2,1,3]

首先，当我们定义好指针，那么两个链表的表现应该是这样的：

//经过第一轮循环链表是如图表现：
while (head) {
  let curry:ListNode = new ListNode(head.val);
  while (newHead.next && newHead.next.val < head.val) {
    newHead = newHead.next;
  }
//第8、9行代码用于插入指针，这是单链表的经典操作
  curry.next = newHead.next;
  newHead.next = curry;
  head = head.next;
  newHead = preNewHead;
}

//经过第二轮循环链表是如图表现：
while (head) {
  let curry:ListNode = new ListNode(head.val);
  while (newHead.next && newHead.next.val < head.val) {
    newHead = newHead.next;
  }
//第8、9行代码用于插入指针，这是单链表的经典操作
  curry.next = newHead.next;
  newHead.next = curry;
  head = head.next;
  newHead = preNewHead;
}

所以说我们只需要不停的判断head指针，他不指向空，我们就不断的进行循环，直到他指向null，意味着链表遍历完了，这个时候我们return新链表即可，return的时候需要注意，我们定义的是一个头结点，而头结点的next节点才是题目给到我们链表的第一个节点，所以需要return 头结点的next节点出去

代码

function insertionSortList(head: ListNode | null): ListNode | null {
  if (head == null) return null;
  let newHead: ListNode = new ListNode();
  let preNewHead: ListNode = newHead;
  // let dummy: ListNode = head;
  while (head) {
    let curry:ListNode = new ListNode(head.val);
    while (newHead.next && newHead.next.val < head.val) {
      newHead = newHead.next;
    }
    curry.next = newHead.next;
    newHead.next = curry;
    head = head.next;
    newHead = preNewHead;
  }
  // head = head.next;
  return preNewHead.next;
}