leetcode 147. Insertion Sort List 链表插入排序

矫情吗；* 2022-06-08 04:58 118阅读 0赞

Sort a linked list using insertion sort.

本题就是要做链表的插入排序。

代码如下：

/*class ListNode 
    {
          int val;
          ListNode next;
          ListNode(int x) { val = x; }
    }*/
    
    /*
     * 链表的插入排序
     * */
    public class Solution 
    {
        public ListNode insertionSortList(ListNode head) 
        {
            if(head==null || head.next==null)
                return head;
    
            ListNode sortHead=new ListNode(-1);
            while(head!=null)
            {
                ListNode cur=sortHead;
                while(cur.next!=null && cur.next.val <= head.val)
                    cur=cur.next;
    
                ListNode tmp=head;
                head=head.next;
    
                //插入到排序好的链表
                tmp.next=cur.next;
                cur.next=tmp;
            }
            return sortHead.next;
        }
    }

下面是C++的做法，就是做一个插入排序，两成循环即可完成本题要求

代码如下：

#include <iostream>
    #include <stack>
    #include <queue>
    
    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 == NULL || head->next == NULL)
                return head;
            ListNode* fin = new ListNode(-1);
            while (head != NULL)
            {
                ListNode* cur = fin;
                while (cur->next != NULL && cur->next->val <= head->val)
                    cur=cur->next;
    
                ListNode* tmp = head;
                head = head->next;
    
                tmp->next = cur->next;
                cur->next = tmp;
            }
            return fin->next;
        }
    };