Insertion Sort List

文章目录

1. Insertion Sort List

Insertion Sort List

题目

Sort a linked list using insertion sort.

思路

插入排序的思想

解题

c++版

/**
 * 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==NULL || head->next==NULL) return head;
        ListNode *cur=head;
        ListNode *helper=new ListNode(0);
        ListNode *pre;
        while(cur)
        {
            ListNode *next=cur->next;
            pre=helper;
            while(pre->next!=NULL && pre->next->val<cur->val)
            {
                pre=pre->next;
            }
            cur->next=pre->next;
            pre->next=cur;
            cur=next;
        }
        return helper->next;
    }
};

Python 版

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param head, a ListNode
    # @return a ListNode
    def insertionSortList(self, head):
        if head == None or head.next == None:
    		return head
    	dummy = ListNode(0)
    	dummy.next = head
    	cur = head
    	while cur.next != None:
    		if cur.next.val < cur.val:
    			pre = dummy
    			while pre.next.val < cur.next.val:
    				pre = pre.next
    			temp = cur.next
    			cur.next = temp.next
    			temp.next = pre.next
    			pre.next = temp
    		else:
    			cur = cur.next
    	return dummy.next