Leetcode147 对链表进行插入排序 (氪金计划启动)

2020年11月20日 0 作者 折纸

题目描述

file

方法一

class Solution {
    public ListNode insertionSortList(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode tail = head;
        ListNode cur = head.next;
        while(cur!=null){
            if(cur.val >= tail.val){
                tail = tail.next;
            }else{
                ListNode prev = dummy;
                while(prev.next.val<=cur.val){
                    prev = prev.next;
                }
                tail.next = cur.next;
                cur.next = prev.next;
                prev.next = cur;
            }
            cur = tail.next;
        }
        return dummy.next;
    }
}

 

思路

  • 链表问题设置哑节点很重要
  • 取cur = tail.next的思想一时半会也没想到,积累经验吧

今天氪金冲会员了,要赚回来呀!

file