[leetcode题解]147.Insertion Sort List

对单链表的排序,前几天写过一篇文章使用o(nlog(n))的时间复杂度进行排序,当时说可选的方法是利用归并或者快排对单链表进行排序,这个题目同样给定一个单链表,只不过这里要求用插入排序对其进行排序。在数组中我们使用插入排序的时候通常在寻找插入位置的时候是从后向前,这样可以同时查找并把较大的元素后移一位,然后腾出要插入的位置,但是在单链表中就不行了,首先,单链表不能逆向遍历,第二,单链表无需移动,可以o(1)插入,所以在单链表中寻找插入位置的时候要从头往后查找,找到插入位置或者直到末尾,那就把该元素直接插入即可。从而最终保证有序。当然顺序查找要插入的位置通常是两个指针,一个遍历,一个记录前驱节点,这里为了方便直接用一个指针写了,但是要注意判断保证逻辑正确。
下面为c++和python代码:

c++代码:

class Solution {
//代码作者:凌风技术站
public:
    ListNode* insertionSortList(ListNode* head) {
        if (head == NULL || head->next == NULL)return head;
        
        ListNode *pre = new ListNode(head->val);
        
        while(head != NULL)
        {
            ListNode *t = head->next;
            ListNode *p = pre;
            while(p->next != NULL)
            {
                if (p->next->val > head->val)
                {
                    head->next = p->next;
                    p->next = head;
                    break;
                }
                p = p->next;
            }
            if (p->next == NULL)
            {
                head->next = p->next;
                p->next = head;
            }
            head = t;
        }
        return pre->next;
    }
};

python代码:

class Solution(object):
    def insertionSortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        :author :凌风技术站
        """
        if head is None or head.next is None:
            return head
            
        pre = ListNode(head.val - 1)
        while head is not None:
            t = head.next
            p = pre
            while p.next is not None:
                if head.val <= p.next.val:
                    head.next = p.next
                    p.next = head
                    break
                p = p.next
            if p.next is None:
                head.next = p.next
                p.next = head
            head = t
        return pre.next

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[leetcode题解]147.Insertion Sort List

本文链接地址:http://www.iaccepted.net/algorithm/leetcode/70.html

相关文章



发表评论

电子邮件地址不会被公开。 必填项已用*标注