单链表的选择排序

真的用链表去做很可能会超时。2333。
简单搜索了一下，基本上都是改变链表每项内部数据的，而不是把链表重新连接。2333。
用例通过率: 100.00% 运行时间: 233ms 占用内存: 11704KB.

#
# 离经叛道的方法
# @param head ListNode类 the head node
# @return ListNode类
#


class Solution:
    def sortInList(self, head):
        li=[]
        li.append(head.val)
        while head.next:
            head = head.next
            li.append(head.val)
        li.sort()
        ln = []
        for i in li:
            n = ListNode(i)
            ln.append(n)
        for i in range(0, len(ln)-1):
            ln[i].next = ln[i+1]
        return ln[0]


class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

正统方法：用例通过率: 100.00% 运行时间: 459ms 占用内存: 1520KB。

#include <stdio.h>
/**
 * 
 * @param head ListNode类 the head node
 * @return ListNode类
 */
struct ListNode *sortInList(struct ListNode *head)
{
    struct ListNode *small, *p, *q;
    int temp;
    // write code here
    for (p = head; p->next != NULL; p = p->next)
    {
        small = p;
        for (q = p->next; q; q = q->next)
        {
            if (q->val < small->val)
            {
                small = q;
            }
        }
        if (small != p)
        {
            temp = p->val;
            p->val = small->val;
            small->val = temp;
        }
    }
    return head;
}