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

This article mainly introduces how to insert and sort the linked list by java. It is very detailed and has a certain reference value. Friends who are interested must finish reading it.

Insert sort the linked list.

The animation of the insertion sort is shown above. Starting with the first element, the linked list can be considered partially sorted (represented in black).

At each iteration, an element (represented in red) is removed from the input data and inserted in place into the sorted linked list.

Insert sorting algorithm:

The insertion sort is iterative, moving only one element at a time until all elements can form an ordered output list.

In each iteration, the insert sort removes only one element to be sorted from the input data, finds its appropriate position in the sequence, and inserts it.

Repeat until all input data has been inserted.

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 insertionSortList (ListNode head) {

2 if (head = = null)

3 return head

4 ListNode helper = new ListNode (0)

5 ListNode cur = head

6 ListNode pre = helper

7 ListNode next = null

8 while (cur! = null) {

9 next = cur.next

10 while (pre.next! = null & & pre.next.val < cur.val) {

11 pre = pre.next

12}

13 cur.next = pre.next

14 pre.next = cur

15 pre = helper

16 cur = next

17}

18 return helper.next

19}

Parsing:

About sorting before we introduced more than a dozen sorting algorithms, here let the use of insert sorting, in fact, insert sorting is not difficult, the difficulty here is the disconnection and reconnection of the linked list. Of course, we can also use other methods, such as we disconnect each node of the linked list, then store it in the array, then sort it, and finally connect all the sorted arrays in order.

The above is all the content of the article "how to insert and sort the linked list by java". Thank you for reading! Hope to share the content to help you, more related knowledge, welcome to follow the industry information channel!

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.