本文共 738 字,大约阅读时间需要 2 分钟。
Sort a linked list using insertion sort.本题很简单,用插入排序方法对链表进行排序。可以构建一个临时的链表,然后将待排序的链表的每一个节点插入到临时链表中。代码如下:
/** * 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) { ListNode tmpNode = ListNode(INT_MIN); if (head == NULL || head->next==NULL){ return head; } while(head){ ListNode * pNode = head; head = head->next; ListNode *pPrev = &tmpNode; ListNode *pNext = pPrev->next; while (pNext && pNext->val < pNode->val) { pPrev = pNext; pNext = pNext->next; } pPrev->next = pNode; pNode->next = pNext; } return tmpNode.next; }};
转载地址:http://wfxti.baihongyu.com/