链表的排序

电玩女神 2022-05-23 01:55 168阅读 0赞

![这里写图片描述][70]

import java.util.*;
    class ListNode {
          int val;
          ListNode next;
          ListNode(int x) {
              val = x;
              next = null;
          }
      }
    
    public class Solution {
    
        //使用1.快慢指针，2.归并排序
        public ListNode sortList(ListNode head) {
            if(head==null||head.next==null)
               return head;
            ListNode mid=getMidNode(head);
            //从中间结点的位置断开
            ListNode midNext=mid.next;
            mid.next=null;
            //归并、合并
            return merge(sortList(head),sortList(midNext));
        }
        //获得中间节点
        public ListNode getMidNode(ListNode head){
              ListNode fast=head;  //快指针
              ListNode slow=head;  //慢指针
              //快走两步，慢走一步
              while(fast.next!=null&&fast.next.next!=null){
                 //偶数时取前一个
                fast=fast.next.next;
                slow=slow.next;
              }
              return slow;
        }
        //归并排序(合并两个已经排序的链表)
        public ListNode merge(ListNode left,ListNode right){
    
              if(left==null)
                 return right;
              if(right==null)
                  return left;
              ListNode first=left.next;
              ListNode second=right.next;
              ListNode res,newHead;
              if(left.val<right.val)
              {
                  newHead=res=left;
                  second=right;
              }else{
                  newHead=res=right;
                  second=left;
              }
              while(first!=null||second!=null){
    
                  if(first==null) //左边链表没有了
                  {
                     res.next=second;
                     return newHead;
                   }else if(second==null)  //右边链表没有了
                   {
                      res.next=first;
                      return newHead;
                   }else if(first.val<second.val)
                   {
                      res.next=first;
                      first=first.next;
                      res=res.next;
                   }else{
                      res.next=second;
                      second=second.next;
                      res=res.next;
                   }
    
              }
              return newHead;
        }
    
        //解法二:快排思想
       public ListNode sortList2(ListNode head) {
             if(head==null||head.next==null)
               return head;
             quickSort(head,null);
             return head;
       }
       public void quickSort(ListNode head,ListNode end){
              if(head!=end){
                ListNode patition=patition(head);
                quickSort(head,patition);
                quickSort(patition.next,end);
              }
       }
       //patition函数
       public ListNode patition(ListNode head){
            ListNode slow=head;
            ListNode fast=head.next;
            while(fast!=null){
                if(fast.val<head.val){
                    slow=slow.next;
                    fast.val=slow.val^fast.val^(slow.val=fast.val);
                }
                fast=fast.next;
            }
            slow.val=head.val^slow.val^(head.val=slow.val);
            return slow;
       }
         //打印链表
        public void printList(ListNode head)
        {
             while(head!=null){
                 System.out.print(head.val);
                 head=head.next;
             }
             System.out.println();
        }
    
        public static void main(String[]args){
           // System.out.println("Hello wolrd!");
            ListNode head=new ListNode(5);
            head.next=new ListNode(3);
            head.next.next=new ListNode(4);
            head.next.next.next=new ListNode(6);
            Solution s=new Solution();
            s.printList(head);
            s.printList(s.sortList2(head));
        }
    }

[70]: /images/20220523/b07b8297a2ab4e2db09a420603355fdd.png