Leetcode -- Insertion Sort List

题目：

Sort a linked list using insertion sort.

分析：

插入排序。

代码1：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if(!head || !head->next) return head;
        ListNode* l1 = head;
        ListNode* l1_next;
        ListNode* last = l1;
        ListNode* l2 = head->next;
        ListNode* l2_next;

        last -> next = NULL;
        l1->next = NULL;
        while(l2)
        {
            l1 = head;
            l2_next = l2->next;
            while(l1)
            {
                if(last->val <= l2->val)
                {
                    last->next = l2;
                    last = last->next;
                    last->next = NULL;
                    break;
                }
                if(l1->val > l2->val)
                {
                    l2->next = l1;
                    head = l2;
                    break;
                }
                else
                {
                    if(l1->val <= l2->val && l1->next && l1->next->val > l2->val)
                    {
                        l1_next = l1->next;
                        l1->next = l2;
                        l2->next = l1_next;
                        break;
                    }
                    else
                    {
                        l1 = l1->next;
                    }
                }
             }
             l2 = l2_next;
        }
        return head;
    }
};
           

【参考代码：https://leetcode.com/discuss/24663/an-easy-and-clear-way-to-sort-o-1-space】

public ListNode insertionSortList(ListNode head) {
        if( head == null ){
            return head;
        }

        ListNode helper = new ListNode(0); //new starter of the sorted list
        ListNode cur = head; //the node will be inserted
        ListNode pre = helper; //insert node between pre and pre.next
        ListNode next = null; //the next node will be inserted
        //not the end of input list
        while( cur != null ){
            next = cur.next;
            //find the right place to insert
            while( pre.next != null && pre.next.val < cur.val ){
                pre = pre.next;
            }
            //insert between pre and pre.next
            cur.next = pre.next;
            pre.next = cur;
            pre = helper;
            cur = next;
        }

        return helper.next;
    }
           

分析：

思路都是插入排序的思想。代码1比参考代码麻烦的原因是，每次好到插入的地方，就进行插入了。其实，只需要确定插入的地方，然后再进行插入就可以了。没有必要对插入地方进行分类。

其次就是比较的时候，等号的处理。代码1中，是需要考虑这个问题的。