首页 > 代码库 > [Leetcode][JAVA] Merge Two Sorted Lists & Sort List
[Leetcode][JAVA] Merge Two Sorted Lists & Sort List
Merge Two Sorted Lists:
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
两个排好序的链表拼接,只要用两个指针遍历链表即可. 可以借助一个helper指针来进行开头的合并。如果有一个遍历完,则直接把另一个链表指针之后的部分全部接在后面:
1 public ListNode mergeTwoLists(ListNode l1, ListNode l2) { 2 ListNode helper = new ListNode(0); 3 ListNode cur1 = l1; 4 ListNode cur2 = l2; 5 ListNode cur = helper; 6 while(cur1!=null || cur2!=null) 7 { 8 if(cur1==null) 9 {10 cur.next = cur2;11 break;12 }13 if(cur2==null)14 {15 cur.next = cur1;16 break;17 }18 if(cur1.val<=cur2.val)19 {20 cur.next = cur1;21 cur1=cur1.next;22 }23 else24 {25 cur.next = cur2;26 cur2=cur2.next;27 }28 cur=cur.next;29 }30 return helper.next;31 }
Sort List:
Sort a linked list in O(n log n) time using constant space complexity.
有了Merged Two Sorted Lists的基础,这题就很好写了。提到O(nlogn)的排序算法,马上想到快排和合并排序,不过快排不稳定而且对于链表来说交换不方便,所以还是决定采用merge sort.
对于链表,merge sort中的split过程可以使用快慢指针实现,比较简单易懂:
1 public ListNode sortList(ListNode head) { 2 return mergeSort(head); 3 } 4 5 public ListNode mergeSort(ListNode start) 6 { 7 if(start==null) return null; 8 if(start.next==null) return start; 9 10 ListNode slow = start;11 ListNode fast = start;12 while(fast!=null && fast.next!=null && fast.next.next!=null)13 {14 slow = slow.next;15 fast = fast.next.next;16 }17 ListNode second = slow.next;18 slow.next = null;19 return mergeTwoLists(mergeSort(start), mergeSort(second));20 }21 public ListNode mergeTwoLists(ListNode l1, ListNode l2) {22 ListNode helper = new ListNode(0);23 ListNode cur1 = l1;24 ListNode cur2 = l2;25 ListNode cur = helper;26 while(cur1!=null || cur2!=null)27 {28 if(cur1==null)29 {30 cur.next = cur2;31 break;32 }33 if(cur2==null)34 {35 cur.next = cur1;36 break;37 }38 if(cur1.val<=cur2.val)39 {40 cur.next = cur1;41 cur1=cur1.next;42 }43 else44 {45 cur.next = cur2;46 cur2=cur2.next;47 }48 cur=cur.next;49 }50 return helper.next;51 }
[Leetcode][JAVA] Merge Two Sorted Lists & Sort List
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。