LeetCode -- Insertion Sort List
題目描述：
Sort a linked list using insertion sort.
思路：
實現一個插入排序list類，遍歷鏈表逐個添加到list，使用list創建新鏈表。
實現代碼：
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode InsertionSortList(ListNode head) {
if(head == null || head.next == null){
return head;
}
var list = new SortedNodes();
while(head != null){
list.Add(head.val);
head = head.next;
}
ListNode h = null;
ListNode node = null;
var c = 0;
foreach(var n in list.Nodes){
if(c == 0){
node = new ListNode(n);
h = node;
}else{
node.next = new ListNode(n);
node = node.next;
}
c++;
}
return h;
}
public class SortedNodes{
private IList _nodes;
public SortedNodes(){
_nodes = new List();
}
public void Add(int n)
{
for(var i = 0;i < _nodes.Count; i++){
if(n < _nodes[i]){
_nodes.Insert(i,n);
return;
}
}
_nodes.Add(n);
}
public IList Nodes{
get{
return _nodes;
}
}
}
}
