算法（十九）

1、使用插入排序对链表进行排序。

 public ListNode insertionSortList(ListNode head) {

        if(head == null){

            return null;

        }

        ListNode curNode = head.next;

        ListNode pNode = new ListNode(0);

        pNode.next = head;

        head.next = null;

        while(curNode != null){

            ListNode compareNode = pNode;

            while(compareNode != null){

                if(compareNode.next == null || compareNode.next.val>= curNode.val){

                    break;

                }

                compareNode = compareNode.next;

            }

            ListNode temp = curNode.next;

            curNode.next = compareNode.next;

            compareNode.next = curNode;

            curNode = temp;

        }

        return pNode.next;

    } 

2、将给定的单链表L： L 0→L 1→…→L n-1→L n,重新排序为： L 0→L n →L 1→L n-1→L 2→L n-2→…要求使用原地算法，并且不改变节点的值。例如：对于给定的单链表{1,2,3,4}，将其重新排序为{1,4,2,3}.

public void reorderList(ListNode head) {

        if(head == null || head.next == null)

            return;

        // 快满指针找到中间节点

        ListNode fast = head;

        ListNode slow = head;

        while(fast.next != null && fast.next.next != null){

            fast = fast.next.next;

            slow = slow.next;

        }

        // 拆分链表，并反转中间节点之后的链表

        ListNode after = slow.next;

        slow.next = null;

        ListNode pre = null;

        while(after != null){

            ListNode temp = after.next;

            after.next = pre;

            pre = after;

            after = temp;

        }

        // 合并两个链表

        ListNode first = head;

        after = pre;

        while(first != null && after != null){

            ListNode ftemp = first.next;

            ListNode aftemp = after.next;

            first.next = after;

            first = ftemp;

            after.next = first;        

            after = aftemp;        

        }

    }