How to implement sorting linked list by java
This article will explain in detail how to achieve sorted linked lists in java. The editor thinks it is very practical, so I share it for you as a reference. I hope you can get something after reading this article.
The linked list is sorted under O (n log n) time complexity and constant space complexity.
Example 1:
Enter: 4-> 2-> 1-> 3
Output: 1-> 2-> 3-> 4
Example 2:
Enter:-1-> 5-> 3-> 4-> 0
Output:-1-> 0-> 3-> 4-> 5
Answer:
1public ListNode sortList (ListNode head) {
2 if (head = = null | | head.next = = null)
3 return head
4 / / divide the linked list into two parts
5 ListNode prev = null, slow = head, fast = head
6 while (fast! = null & & fast.next! = null) {
7 prev = slow
8 slow = slow.next
9 fast = fast.next.next
10}
11 prev.next = null
12 / / sort the two parts separately
13 ListNode L1 = sortList (head)
14 ListNode L2 = sortList (slow)
15 / / and then merge
16 return merge (L1, L2)
17}
eighteen
19ListNode merge (ListNode L1, ListNode L2) {
20 ListNode l = new ListNode (0), p = l
21 while (L1! = null & & L2! = null) {
22 if (l1.val < l2.val) {
23 p.next = L1
24 L1 = l1.next
25} else {
26 p.next = L2
27 L2 = l2.next
28}
29 p = p.next
30}
31 if (L1! = null)
32 p.next = L1
33 if (L2! = null)
34 p.next = L2
35 return l.next
36}
This is the end of this article on "how to sort linked lists in java". I hope the above content can be of some help to you, so that you can learn more knowledge. if you think the article is good, please share it out for more people to see.
