Sort a linked list using insertion sort.

【题意】

用插入排序对一个链表进行排序。

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

【思路】

基础题。难点在于理解链表结，因为 next 既是当前 node 的属性，又表示下一个 node。

在 head 之前添加一个新的头 newhead，因为插入排序时可能有 node 要插在 head 之前，这时就需要这个 newhead 的帮助。

【Java代码】

public class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) return head;//新手很容易忽略这一行
        
        ListNode newhead = new ListNode(0);
        newhead.next = head;//在head前添加一个新头newhead
        ListNode p = head.next;//遍历从第二个node开始
        head.next = null;//目前已排序的链表只有newhead和head两个结点，这样做的好处是如果后面插入的结点都在head之前，那么可以保证排完序的链表结尾指向null
        
        while (p != null) {//用p遍历还未排序的链表
            
            ListNode cur = p;
            p = p.next;
            cur.next = null;//如果这个结点需要查到链表的最后，这样做可以保证链表结尾指向null
            
            ListNode node = newhead.next;
            ListNode pre = newhead;
            
            while (node != null) {//用node遍历已排好序的链表，pre表示遍历时当前项的前一项
                if (cur.val < node.val) {//在该插入的位置插入cur
                    pre.next = cur;
                    cur.next = node;
                    break;
                } else {//还未到插入的位置，继续向后，同时更新pre
                    pre = node;
                    node = node.next;
                }
                
                if (node == null) {//如果插入的位置在链表末尾
                    pre.next = cur;
                }
            }
        }
        
        return newhead.next;
    }
}

不多说了，捋清思路，分清楚哪个是变量，哪个是链表中的项。混乱时不妨从头再来。

【LeetCode】Insertion Sort List