insertion Sort List (链表的插入排序) leecode java

逻辑简单,代码难写,基础不劳,leecode写注释不能出现中文,太麻烦,我写了大量注释,链表问题最重要的就是你那个指针式干啥的

提交地址https://oj.leetcode.com/problems/insertion-sort-list/

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode insertionSortList(ListNode head) {
    if(head==null) return head;
    ListNode h=new ListNode(-1000000); //加入头结点方面,特别适合头结点不断改变的情况,c++要释放掉,java直接返回头的next就可
    h.next=head;
  ListNode cur=head.next; //cur 保存当前处理的节点
  head.next=null; //别忘了,新链表的尾巴值为空
    while(cur!=null)
    {
        ListNode nextNode=cur.next; //保存下一个要处理的点,因为cur会被插入的新链表中,所以保存,然后赋给cur(最后一句)
        
        ListNode l=h.next;
        ListNode pre=h;
        while(l!=null) //找到合适的插入位置,找pre地址
        {
            if(l.val<=cur.val)
            {
                pre=l;
                l=l.next;
            }
            else
            {
                break;
            }
        }
            
        
        //insert into the list
        cur.next=pre.next;
        pre.next=cur;
        
        
        
        
        cur=nextNode;
        
        
        
    }
    
    
         return h.next;
        
    }
   
    
    
    
}

 

insertion Sort List (链表的插入排序) leecode java,布布扣,bubuko.com

insertion Sort List (链表的插入排序) leecode java

上一篇:在Spring中轻松写日志


下一篇:Python分布式+云计算