首页 > 代码库 > [leetcode]Insertion Sort List

[leetcode]Insertion Sort List

2024-07-13 06:00:36   225人阅读

Insertion Sort List

Sort a linked list using insertion sort.

 

算法思路：

最基本的插入排序，时间复杂度O(n*n)，空间复杂度O(1)

代码：

 1 public class Solution { 2     public ListNode insertionSortList(ListNode head) { 3         if(head == null || head.next == null) return head; 4         ListNode list = new ListNode(0); 5         list.next = head; 6         head = head.next; 7         list.next.next = null; 8         while(head != null){ 9             ListNode tail = list;10             ListNode node = head;11             head = head.next;12             node.next = null;13             while(tail != null){14                 if(tail.next == null){15                     tail.next = node;16                     break;17                 }18                 if(tail.next.val > node.val){19                     node.next = tail.next;20                     tail.next = node;21                     break;22                 }else{23                     tail = tail.next;24                 }25             }26         }27         return list.next;28     }29 }


联系
我们