LeetCode Insertion Sort List

· 399 words · 1 minute read
2017年7月
LeetCode

147.Insertion Sort List

Sort a linked list using insertion sort.

方法

做链表题目的时候一定要注意链表尾部的值。假设链表为4->2->1。步骤：

  1. 生成新的链表头结点-1。 -1->null。
  2. 若链表的next节点为null,则直接加入原链表的第一个节点，如：1->4->null。若链表的next不为null并且新链表的值小于当前旧链表的值，那么循环新链表的next，直到新链表的next为null或者新链表的next的值>旧链表当前的值，如：1->2->4->null。

  3. 返回新链表的next节点。

    /**

    • Definition for singly-linked list.
    • public class ListNode {
    • int val;
    • ListNode next;
    • ListNode(int x) { val = x; }

    • } */ public class Solution { public ListNode insertionSortList(ListNode head) { if(head == null){ return null; }

      ListNode ln = new ListNode(-1);
ListNode newLn = ln;
ListNode cur = head;

while(cur != null){
    ListNode next = cur.next;
    //循环找到新插入的点在newLn的位置
    while(newLn.next != null && newLn.next.val < cur.val){
        newLn = newLn.next;
    }
    //cur设置为newLn的next值，一开始为null
    cur.next = newLn.next;
    newLn.next = cur;
    cur = next;
    //重定位newLn为一开始的位置
    newLn = ln;
}
return newLn.next;

      } }

Share