对一个链表进行插入排序

灰太狼 2022-05-23 02:50 281阅读 0赞

这里写图片描述

class ListNode {
      int val;
      ListNode next;
      ListNode(int x) {
          val = x;
         next = null;
      }
  }
public class Solution {
    public ListNode insertionSortList(ListNode head) {
        if(head==null||head.next==null)
          return head;
        ListNode tmp1=head;
        ListNode tmp2=head.next;
        while(tmp1.next!=null)
        {
              while(tmp2!=null)
              {
                  if(tmp2.val<tmp1.val)
                  {
                      int tmp=tmp2.val;
                      tmp2.val=tmp1.val;
                      tmp1.val=tmp;
                  }
                  tmp2=tmp2.next;
              }
              tmp1=tmp1.next;
              tmp2=tmp1.next;
        }
        return head;
    }
    //打印链表
    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(4);
        head.next.next=new ListNode(3);
        Solution s=new Solution();
        //s.printList(head);
        s.printList(s.insertionSortList(head));
    }
}