链表的直接插入排序 Insertion Sort List

/**
 * Created by chris on 14/11/16.
 * <p/>
 * 链表,直接插入排序
 * <p/>
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode(int x) {
 * val = x;
 * next = null;
 * }
 * }
 */
public class InsertionSortList {
    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode p = head;//用来遍历待排序的链表
        ListNode pSorted = null;//用来遍历已经排好序的链表
        ListNode pre = null;//pSorted的前一个节点
        ListNode pNext = null;//p 的下一个节点


        ListNode h = new ListNode(-1);//sorted head
        p = head;
        if (h.next == null) {
            h.next = p;
            p = p.next;
            h.next.next = null;
            pSorted = h.next;
            pre = h;
        }
        while (p != null) {

            while (pSorted != null && p.val > pSorted.val) {
                pre = pSorted;
                pSorted = pSorted.next;
            }
            pre.next = p;
            pNext = p.next;
            p.next = pSorted;
            p = pNext;
            pSorted = h.next;
            pre = h;

        }

        return h.next;

    }
}
Tagged on: , , ,

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>