By Long Luo
148. 排序链表 。
暴力 + ArrayList
思路与算法:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
| public ListNode sortList(ListNode head) { if (head == null || head.next == null) { return head; }
ListNode pNode = head;
List<Integer> nodeList = new ArrayList<>(); while (pNode != null) { nodeList.add(pNode.val); pNode = pNode.next; }
Collections.sort(nodeList);
ListNode dummyNode = new ListNode(-1); pNode = dummyNode; for (int i = 0; i < nodeList.size(); i++) { pNode.next = new ListNode(nodeList.get(i)); pNode = pNode.next; }
return dummyNode.next; }
|
123
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
| public ListNode sortList(ListNode head) { if (head == null || head.next == null) { return head; }
ListNode pNode = head;
List<ListNode> nodeList = new ArrayList<>(); while (pNode != null) { nodeList.add(pNode); pNode = pNode.next; }
nodeList.sort(Comparator.comparingInt(o -> o.val));
ListNode dummyNode = new ListNode(-1); ListNode preNode = dummyNode; for (int i = 0; i < nodeList.size(); i++) { pNode = nodeList.get(i); preNode.next = pNode; pNode.next = null; preNode = pNode; }
return dummyNode.next; }
|
复杂度分析
- 时间复杂度:O(nlogn+n)
- 空间复杂度:O(n)
归并排序
复杂度分析
- 时间复杂度:O(nlogn+n)
- 空间复杂度:O(n)
All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions. 😉😃💗