首页 > 代码库 > [Leetcode][JAVA] Insertion Sort List
[Leetcode][JAVA] Insertion Sort List
Sort a linked list using insertion sort.
简单插入排序，先写个插入一个值到链表里的函数，再遍历整个链表，一个一个把值插入新链表中：
1 public ListNode insertionSortList(ListNode head) { 2 if(head==null) 3 return null; 4 ListNode re = new ListNode(head.val); 5 ListNode cur = head.next; 6 while(cur!=null) 7 { 8 re = insert(re, cur.val); 9 cur = cur.next;10 }11 return re;12 }13 14 public ListNode insert(ListNode head, int v)15 {16 ListNode ln = new ListNode(v);17 ListNode cur = head;18 ListNode helper = new ListNode(0);19 helper.next = head;20 ListNode pre = helper;21 22 while(cur!=null)23 {24 if(v<cur.val)25 {26 pre.next = ln;27 ln.next = cur;28 return helper.next;29 }30 pre = cur;31 cur = cur.next;32 }33 pre.next = ln;34 ln.next = null;35 return helper.next;36 }
递归实现：
1 public ListNode insertionSortList(ListNode head) { 2 if(head==null || head.next==null) 3 return head; 4 int value =http://www.mamicode.com/ head.val; 5 return insert(insertionSortList(head.next),value); 6 } 7 8 public ListNode insert(ListNode head, int v) 9 {10 ListNode ln = new ListNode(v);11 ListNode cur = head;12 ListNode helper = new ListNode(0);13 helper.next = head;14 ListNode pre = helper;15 16 while(cur!=null)17 {18 if(v<cur.val)19 {20 pre.next = ln;21 ln.next = cur;22 return helper.next;23 }24 pre = cur;25 cur = cur.next;26 }27 pre.next = ln;28 ln.next = null;29 return helper.next;30 }
[Leetcode][JAVA] Insertion Sort List
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。