P147 Insertion Sort List

2019-11-06 06:56:40

字体：大中小

来源：转载

供稿：网友

问题描述:

Sort a linked list using insertion sort. 对链表进行插入排序。

思路：

代码实现：

// ListNode 的定义 class ListNode { int val; ListNode next; ListNode(int x) { val = x; next = null; } } public ListNode insertionSortList(ListNode head) { ListNode curNode = head; ArrayList<ListNode> arr = new ArrayList<ListNode>(); while(curNode != null) { arr.add(curNode); int value = curNode.val, i; for(i = arr.size()-2; i>=0; i--){ if(value < arr.get(i).val) arr.get(i+1).val = arr.get(i).val; else break; } arr.get(i+1).val = value; curNode = curNode.next; } return head; } public ListNode insertionSortList2(ListNode head) { ListNode newHead = new ListNode(0), curNode, PRe; while(head != null) { pre = head; head = head.next; curNode = newHead; while(curNode.next != null && pre.val > curNode.next.val ) { curNode = curNode.next; } pre.next = curNode.next; curNode.next = pre; } return newHead.next; }

上一篇：第一周 leetcode 224. Basic Calculator（hard）

下一篇：获取客户区大小的办法