单链表的排序

链表的排序

参考大佬的代码做了一点总结

• 算法
  • 虚假的选择排序：交换链表中的值

    public ListNode sortInList (ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode move = head;
        while (move.next != null) {
            ListNode temp = move.next;
            while (temp != null) {
                if (temp.val < move.val) {
                    int val = temp.val;
                    temp.val = move.val;
                    move.val = val;
                }
                temp = temp.next;
            }
            move = move.next;
        }
        return head;
    }

• 算法
  • 真正的选择排序
  • 1.建立哨兵节点
  • 2.每次从未排序的链表节点中找出最小的节点接到已排序链表的后面

    public ListNode sortInList (ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode sorted = dummy;

        while (sorted.next != null) {
            ListNode pre = sorted;
            ListNode cur = sorted.next;
            ListNode preMin = null;
            ListNode min = null;
            while (cur != null) {
                if (min == null || cur.val < min.val) {
                    preMin = pre;
                    min = cur;
                }
                pre = pre.next;
                cur = cur.next;
            }

            preMin.next = min.next;
            min.next = sorted.next;
            sorted.next = min;
            sorted = min;
        }
        return dummy.next;
    }

• 算法
  • 归并排序
  • 1.快慢指针分割链表
  • 2.递归分割
  • 3.合并链表

    public ListNode sortInList (ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        return mergeSort(head);
    }

    public ListNode mergeSort(ListNode head) {
        if (head.next == null) {
            return head;
        }

        ListNode slow = head, fast = head, pre = null;
        while (fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        pre.next = null;
        ListNode left = mergeSort(head);
        ListNode right = mergeSort(slow);
        return merge(left, right);
    }
    public ListNode merge(ListNode left, ListNode right) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while (left != null && right != null) {
            if (left.val < right.val) {
                cur.next = left;
                left = left.next;
            } else {
                cur.next = right;
                right = right.next;
            }
            cur = cur.next;
        }
        if (left != null) {
            cur.next = left;
        }
        if (right != null) {
            cur.next = right;
        }
        return dummy.next;
    }

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList (ListNode head) {
        // write code here
        ArrayList<Integer> arr=new ArrayList<>();
        while (head!=null){
            arr.add(head.val);
            head=head.next;
        }
        Collections.sort(arr);
        ListNode ans=new ListNode(0);
        ListNode cur=ans;
       // ListNode node=ans;
        for (int i=0;i<arr.size();i++){
            cur.next=new ListNode(arr.get(i));
            cur=cur.next;
        }
        return ans.next;
    }
}

import java.util.*;

public class Solution {
    public ListNode sortInList (ListNode head) {
        ArrayList<Integer> al = new ArrayList<Integer>();
        ListNode p = head;
        while (p != null) {
            al.add(p.val);
            p = p.next;
        }
        p = head;
        Collections.sort(al);
        for (int i = 0; i < al.size(); i++) {
            p.val = al.get(i);
            p = p.next;
        }
        return head;
    }
}

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    static bool cmp(ListNode* a,ListNode* b){
        return a->val < b->val;
    }
    ListNode* sortInList(ListNode* head) {
        // write code here
        vector<ListNode*> nums;
        while(head != nullptr){
            nums.push_back(head);
            head = head->next;
        }
        sort(nums.begin(), nums.end() ,cmp);
        for(int i = 0; i < nums.size(); i++){
            nums[i]->next = nums[i+1];
        }
        nums[nums.size()-1]->next = nullptr;
        return nums[0];
        
    }
};

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList (ListNode head) {
        // write code here
        return mergerSort(head);
        
    }
    public ListNode mergerSort(ListNode head){
        if(head == null || head.next == null){
            return head;
        }
        ListNode slow = head;
        ListNode fast = head.next.next;
        ListNode left, right;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode next = slow.next;
        //       slow
        //       mid next
        // 1 3 4 [5] | 6  7 4 2
        slow.next = null;
        left = mergerSort(head);
        right = mergerSort(next);
        
        return mergeList(left, right);
    }
     // dh ->
     // 1 2 3 4
     // 6 7 8 9
     public ListNode mergeList(ListNode left, ListNode right){
         ListNode dummyHead = new ListNode(0);
         ListNode cur = dummyHead;
        //ListNode cur = left.val < right.val ? left : right;
        
         while(left != null && right != null){
             if(left.val < right.val){
                 cur.next = left;
                 left = left.next;
             }
             else{
                 cur.next = right;
                 right = right.next;
             }
             cur = cur.next;
         }
         cur.next = left == null ? right : left;
         
         return dummyHead.next;
    }
    
    
    
}

class Solution:
    def sortInList(self , head: ListNode) -> ListNode:
        # write code here
        p = q =ListNode(0)
        a = []
        while head: # 将链表值赋给列表中
            a.append(head.val)
            head = head.next
        for i in sorted(a): # 列表排序，再一一赋给单链表
            p.next = ListNode(i)
            p = p.next
        return q.next

善用stl容器。multiset允许默认重复元素，并自动升序排序。由于multiset底层为红黑树实现，所以排序的时间复杂度为logn，之后依据multiset依次调整链表即可。空间复杂度为O(n),时间复杂度为max(O(logn),O(n))=O(n)。

`
class Solution {
public:

ListNode* sortInList(ListNode* head) {
    multiset<int>myset;//multiset允许重复元素,而set  则会覆盖重复元素
    ListNode* p=head;
    while(p!=nullptr){
        myset.insert(p->val);
        p=p->next;
    }
    p=head;
    for(auto it=myset.begin();it!=myset.end();it++){
        p->val=*it;
        p=p->next;
    }
    return head;;
}

};
`

#include <stdlib.h>

int privot(int a[], int low, int high);
void quicksort(int a[], int low, int high);

struct ListNode* sortInList(struct ListNode* head ) {
    // write code here
    int s[100000] = {0};
    int i = 0;
    struct ListNode *p = head;

    //将每个节点的val存入数组s中
    while (p) {
        s[i++] = p->val;
        p = p->next;
    }
    
    //快排
    quicksort(s, 0, i-1);
    p = head;
    i = 0;

    //重新给链表赋值val
    while (p) {
        p->val = s[i++];
        p = p->next;
    }

    return head;
}
//划分
int privot(int a[], int low, int high){
    int temp = a[low];
    while (low < high) {
        while (low < high && a[high] >= temp) high--;
        a[low] = a[high];
        while (low < high && a[low] <= temp) low++;
        a[high] = a[low];
    }
    a[low] = temp;
    return low;
}
//快排
void quicksort(int a[], int low, int high){
    if (low < high) {
        int pri = privot(a, low, high);
        quicksort(a, low, pri-1);
        quicksort(a, pri+1, high);
    }
}

    public ListNode sortInList (ListNode head) {
        // write code here
        ListNode cur=head;
        List<Integer> list=new ArrayList<>();
        while(cur!=null){
            list.add(cur.val);
            cur=cur.next;
        }
        Collections.sort(list);
        ListNode fake=new ListNode(1);
        ListNode last=fake;
        for(int i=0;i<list.size();i++){
            ListNode node=new ListNode(list.get(i));
            last.next=node;
            last=node;
        }
        return fake.next;
    }

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */

class Solution {
  public:
    /**
     *
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    ListNode* sortInList(ListNode* head) {
        // 时间复杂度O(NlogN)，空间复杂度O(logN)
        if (head == NULL || head->next == NULL) return head;
        ListNode* left = head, *pre = NULL, *mid = head, *right = head;
        while (right && right->next) {
            pre = mid;
            mid = mid->next;
            right = right->next->next;
        }
        pre->next = NULL;
        return merge(sortInList(left), sortInList(mid));
    }
    ListNode* merge(ListNode* p1, ListNode* p2) {
        ListNode* dummy = new ListNode(-1), *cur = dummy;
        while (p1 && p2) {
            if (p1->val < p2->val) {
                cur->next = p1;
                p1 = p1->next;
            } else {
                cur->next = p2;
                p2 = p2->next;
            }
            cur = cur->next;
        }
        if (p1) cur->next = p1;
        if (p2) cur->next = p2;
        return dummy->next;
    }
};

class Solution {
public:
    ListNode* sortInList(ListNode* head) {
        // 1. 
        vector<ListNode*> nums;
        while (head) {
            nums.emplace_back(head);
            head = head->next;
        }
        
        // 2. 
        std::sort(nums.begin(), nums.end(), [](ListNode* l1, ListNode* l2) {
            return l1->val <= l2->val;
        });
        
        // 3. 
        int n = nums.size();
        for (int i = 0; i < n - 1; ++i) {
            nums[i]->next = nums[i + 1];
        }
        nums[n - 1]->next = nullptr;
        
        return nums[0];
    }
};