首页 > 代码库 > Insertion Sort List
Insertion Sort List
Insertion Sort List
Sort a linked list using insertion sort.
这道题用两个链表做的，这样方便一点。还有新链表头结点我没有存放内容，这样也比较方便，后面返回head1.next就好了
1 /** 2 * Definition for singly-linked list. 3 * public class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode(int x) { 7 * val = x; 8 * next = null; 9 * }10 * }11 */12 public class Solution {13 public ListNode insertionSortList(ListNode head) {14 ListNode head1 = new ListNode(0);15 if(null == head || null == head.next)16 return head;17 18 else{ 19 ListNode temp = new ListNode(0);20 temp.val = head.val;21 temp.next = null;22 head1.next = temp;//用一个新链表23 24 ListNode ptr = head.next;25 while(ptr != null){ //遍历原来的链表，插入到新链表中26 temp = head1.next;27 ListNode tempPre = head1; //temp前面的节点28 while(temp != null){29 if(temp.val > ptr.val){ //在temp前面插入结点30 ListNode nodeAdd = new ListNode(0);31 nodeAdd.val = ptr.val;32 nodeAdd.next = temp;33 tempPre.next = nodeAdd;34 break; //插入完成，跳出循环35 }36 temp = temp.next;37 tempPre = tempPre.next;38 }39 if(null == temp){ //在新链表添加节点40 ListNode nodeAdd = new ListNode(0);41 nodeAdd.val = ptr.val;42 nodeAdd.next = null;43 tempPre.next = nodeAdd;44 }45 ptr = ptr.next;46 }47 }48 49 return head1.next;50 }51 }
Insertion Sort List
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。