首页 > 代码库 > [Leetcode][JAVA] Merge Two Sorted Lists & Sort List

[Leetcode][JAVA] Merge Two Sorted Lists & Sort List

2024-07-22 14:17:17   217人阅读

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


联系
我们