[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;
}