LeetCode——Insertion Sort List

LeetCode——Insertion Sort List

Question

Sort a linked list using insertion sort.

Solution

我的解法，假设第一个节点都比其他节点小，这样感觉好移动指针一些，所以添加了一个额外的最小的节点。

Code

class Solution {

public:

    ListNode *insertionSortList(ListNode *head) {

        if (head == NULL)

            return head;

        ListNode* first = new ListNode(INT_MIN);

        first->next = head;

        head = first;

        ListNode* p2 = head->next;

        ListNode* p2pre = p2;

        while (p2) {

            ListNode* p1 = head;

            ListNode* p1pre = p1;

            while (p1 != p2) {

                if (p1->val > p2->val) {

                	p2pre->next = p2->next;

                    p1pre->next = p2;

                    p2->next = p1;

                    p2 = p2pre;

                    break;

                } else {

                    p1pre = p1;

                    p1 = p1->next;

                }

            }

            p2pre = p2;

            p2 = p2->next;

        }

        return head->next;

    }

};