LeetCode Insertion Sort List 最新题解 - c++编程基础

Sort a linked list using insertion sort.

题目很短，注意：画图，解决边界，特殊情况。插入指针的时候要注意保存原来node的next，这个很容易出错。

一定要优先考虑到头指针和尾指针和空指针的情况。

下面给出完整程序了：

#include  
#include  
#include  
  
using namespace std;  
  
struct ListNode {  
    int val;  
    ListNode *next;  
    ListNode(int x) : val(x), next(NULL) {}  
};  
  
class Solution {  
public:  
    ListNode *insertionSortList(ListNode *head) {  
        if(!head) return nullptr;  
        ListNode *newH = new ListNode(head->val);  
        ListNode *headTemp = head->next;  
  
        while (headTemp)  
        {             
            insertNode(newH, headTemp);  
        }  
        return newH;  
    }  
  
    ListNode *findListPos(ListNode *(&h), ListNode *(&node))  
    {  
        ListNode *htemp = h;  
        while (htemp->next && htemp->next->val <= node->val)  
        {  
            htemp = htemp->next;  
        }  
        return htemp;  
    }  
  
    void insertNode(ListNode *(&h),ListNode *(&node))  
    {  
        if(!node) return;  
        if (!h || node->




val < h->val)  
        {  
            //注意：那里都要注意保存->next的值之后再插入  
            ListNode *nodeNext = node->next;  
            node->next = h;  
            h = node;  
            node = nodeNext;  
            return;  
        }  
        //注意这里的插入操作，很麻烦，一定要熟悉！！！  
        ListNode *htemp = findListPos(h, node);  
        ListNode *saveNode = htemp->next;  
        ListNode *nodeNext = node->next;  
        htemp->next = node;  
        node->next = saveNode;  
        node = nodeNext;  
    }  
};  
  
int main()  
{  
    ListNode t1(3);  
    ListNode t2(4);  
    ListNode t3(1);  
    t1.next = &t2;  
    t2.next = &t3;  
    ListNode *h = &t1;  
    while (h)  
    {  
        cout<val<<" ";  
        h = h->next;  
    }  
    cout<val<<" ";  
        h = h->next;  
    }  
    cout<