147. 对链表进行插入排序

题目描述

原题
对链表进行插入排序。
插入排序的动画演示如上。从第一个元素开始,该链表可以被认为已经部分排序(用黑色表示)。
每次迭代时,从输入数据中移除一个元素(用红色表示),并原地将其插入到已排好序的链表中。
插入排序算法:
    1.
    插入排序是迭代的,每次只移动一个元素,直到所有元素可以形成一个有序的输出列表。
    2.
    每次迭代中,插入排序只从输入数据中移除一个待排序的元素,找到它在序列中适当的位置,并将其插入。
    3.
    重复直到所有输入数据插入完为止。
示例 1:
1
输入: 4->2->1->3
2
输出: 1->2->3->4
Copied!
示例 2:
1
输入: -1->5->3->4->0
2
输出: -1->0->3->4->5
Copied!

题解

1
/**
2
* Definition for singly-linked list.
3
* public class ListNode {
4
* int val;
5
* ListNode next;
6
* ListNode() {}
7
* ListNode(int val) { this.val = val; }
8
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
* }
10
*/
11
class Solution {
12
public ListNode insertionSortList(ListNode head) {
13
if(head==null)return null;
14
ListNode dummyNode = new ListNode();
15
dummyNode.next = head;
16
ListNode curr = head.next;
17
head.next = null;
18
while(curr!=null){
19
ListNode node = dummyNode;
20
while(node.next!=null && node.next.val <= curr.val){
21
node = node.next;
22
}
23
ListNode next = node.next;
24
node.next = curr;
25
ListNode currNext = curr.next;
26
curr.next = next;
27
curr = currNext;
28
}
29
return dummyNode.next;
30
31
}
32
}
Copied!
最近更新 3mo ago
复制链接