[LeetCode] Insertion Sort List 单向链表插入排序

声明：原题目转载自LeetCode，解答部分为原创

Problem ：

Sort a linked list using insertion sort.

Subscribe to see which companies asked this question.

Solution：

        思路：单向链表的插入排序，经典题型。难点是指针的应用，特别是当我们需要用到多个指针来记录 目标节点和比较节点 的前后节点的地址的时候，特别要注意保持思路清晰，避免造成指针指向错误。

        代码如下：

#include<iostream>
using namespace std;

//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) 
            return NULL;
            
        if(head->next == NULL)
            return head;
            
        ListNode *pre_head = new ListNode(-1);  
        pre_head->next = head;  
        ListNode *pre = head;  
        ListNode *cur = pre->next;
		  
        while(cur != NULL)
		{  
            if(cur->val < pre->val)
			{  
                ListNode *pre_i = pre_head;  
                ListNode *cur_i = pre_head->next;
                
                while(cur_i->val < cur->val)
				{  
                    pre_i = cur_i;  
                    cur_i = cur_i->next;  
                }  
                pre->next = cur->next;  
                cur->next = cur_i;  
                pre_i->next = cur;  
                cur = pre->next;
                continue;
            }
			 
            pre = cur;  
            cur = cur->next;   
        }  
        head = pre_head->next;  
        return head;  
    }
};

int main()
{
	ListNode * head = new ListNode(3);
	ListNode * one = new ListNode(2);
	ListNode * two = new ListNode(4);
	head->next = one;
	one->next = two;
	
	Solution text;
	ListNode * output = text.insertionSortList(head);
	
	while(output)
	{
		cout << output->val << " ";
		output = output->next;
	}
	return 0;
}