insertion-sort-list

题目描述

Sort a linked list using insertion sort.

思路

新建一个链表,从原来的表中不断的取数据,再插入的过程中保证有序。

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode(0);
        ListNode p = head;
        while (p!=null){
            ListNode next = p.next;
            insert(dummy,p);
            p = next;
        }
        return dummy.next;
    }
    //dummy 是已经排序好的链表,第一个节点不用
    private void  insert(ListNode dummy,ListNode node){
        ListNode p = dummy;
        while (p.next!=null&& p.next.val<node.val){
            p=p.next;
        }
        ListNode next = p.next;
        p.next=node;
        node.next=next;
    }
}