链表插入排序

题意

用插入排序对链表排序

样例

给予 1->3->2->0->null, 返回 0->1->2->3->null

思路

将接受到的链表当做未排序链表,再创建一个链表存放已排序链表,并创建一个已排序链表的指针。

依次将未排序链表的元素与已排序链表中的每一个元素进行比较(也就是先用未排序链表的第一个与已排序链表的每一个进行比较,然后用未排序链表的第二个,第三个….依次进行比较,直到最后一个元素)

由于题意是升序排序,所以只要未排序链表中的元素大于已排序链表中的元素,那么就将未排序链表的这个元素放到第一个比它大的已排序链表的后面。

要注意的是,将未排序链表的元素放到已排序链表时,不要覆盖掉原数据(先挪动其他数据再进行插入操作)。

代码实现

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
27
28
29
30
31
/**
* Definition for ListNode.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int val) {
* this.val = val;
* this.next = null;
* }
* }
*/
public class Solution {
/**
* @param head: The first node of linked list.
* @return: The head of linked list.
*/
public ListNode insertionSortList(ListNode head) {
ListNode dummy = new ListNode(0);
while (head != null) {
ListNode node = dummy;
while (node.next != null && node.next.val < head.val) {
node = node.next;
}
ListNode temp = head.next;
head.next = node.next;
node.next = head;
head = temp;
}
return dummy.next;
}
}

原题地址

LintCode:链表插入排序

坚持原创技术分享,您的支持将鼓励我继续创作!