首页 > ACM题库 > LeetCode > LeetCode-Insertion Sort List[排序]
2014
11-18

LeetCode-Insertion Sort List[排序]

Insertion Sort List

Sort a linked list using insertion sort.

标签: Linked List Sort
分析

代码1

// LeetCode, Insertion Sort List
// 时间复杂度O(n^2),空间复杂度O(1)
class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        ListNode dummy(INT_MIN);
        //dummy.next = head;

        for (ListNode *cur = head; cur != nullptr;) {
            auto pos = findInsertPos(&dummy, cur->val);
            ListNode *tmp = cur->next;
            cur->next = pos->next;
            pos->next = cur;
            cur = tmp;
        }
        return dummy.next;
    }

    ListNode* findInsertPos(ListNode *head, int x) {
        ListNode *pre = nullptr;
        for (ListNode *cur = head; cur != nullptr && cur->val <= x;
            pre = cur, cur = cur->next)
            ;
        return pre;
    }
};

Java代码:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
   public static ListNode insertionSortList(ListNode head) {
        if(head == null) return head;
        ListNode minHead = new ListNode(Integer.MIN_VALUE);
        ListNode last = head;
        while(last != null){
        	ListNode nextNode = last.next;
        	ListNode insertNode = minHead;//在哪个节点后面插入. 
        	while(insertNode.next != null){
        		if(last.val < insertNode.next.val)
        			break;
        		insertNode = insertNode.next;
        	}
        	last.next = insertNode.next;
        	insertNode.next = last;
        	last = nextNode;
        }
        return minHead.next;
	}
}

  1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  2. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n

  3. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept