Shulou(Shulou.com)06/01 Report--

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.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.