链表的排序和分隔

1.问题描述：链表排序
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
示例 :
输入: 4->2->1->3
输出: 1->2->3->4
2.算法描述
2.1插入排序
leetcode上是对链表插入排序这个题目在前面，结果我先做了链表的排序，结果就用了同一个算法，后面看题解才发现我自己漏了= _ =。算法其实很简单，就是从原先的链表中取出一个元素，根据节点的大小插入到一个新链表的准确位置。
如动图所示:
代码如下：

/**
 * 链表定义.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
   public ListNode sortList(ListNode head) {
		if (head == null || head.next == null) {
			return head;
		}
		
		ListNode l1 = new ListNode(0);
		ListNode pre = l1, temp = head, tc = null, tl = null;
		//先直接插入一个节点
		pre.next = temp;
		temp = temp.next;
		pre.next.next = null;
		
		while (temp != null) {//插入后续节点
			tl = pre;
			tc = pre.next;	
			//寻找新链表中合适的位置进行插入
			while ((tc != null) && (temp.val >= tc.val)) {	
				tc = tc.next;
				tl = tl.next;
			}
			tl.next = temp;
			temp = temp.next;
			tl.next.next = tc;
		}
		return l1.next;
	}
}

这样排序的话，需要至少遍历一次链表，如果新链表不需要进行查找，则时间复杂度最低为O(n)，最高则每次都要查找到新链表的末端，时间复杂度为O(n+1…+n-1+n)=O(n+n*(n+1)/2)，空间复杂度则为O（1）
2.1归并排序
在看了题解之后，发现链表排序用归并排序会更近，虽然空间复杂度会增加。算法解释如下：
将链表平均分成两个等长的链表进入递归，直至划分的链表长度为2时进行排序，递归返回，然后将递归排序完的链表一次排序组合，直至递归完成。图解如下:

class Solution {
    public ListNode sortList(ListNode head) {
    	//特殊情况判断
        if (head == null || head.next == null)
            return head;
        
        //快慢指针寻找中间节点
        ListNode fast = head.next, slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        //找到中点，截断链表
        ListNode tmp = slow.next;
        slow.next = null;
        //进入递归
        ListNode left = sortList(head);
        ListNode right = sortList(tmp);
        ListNode h = new ListNode(0);
        ListNode res = h;
        //排序合并
        while (left != null && right != null) {
            if (left.val < right.val) {
                h.next = left;
                left = left.next;
            } else {
                h.next = right;
                right = right.next;
            }
            h = h.next;
        }
        h.next = left != null ? left : right;
        return res.next;
    }
}

这样的算法复杂度是O(n*logn)，空间复杂度则为O(logn)，如果希望空间复杂度也为O（1），则改变函数变为非递归形式即可。
3.相似问题：链表分隔
给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例:
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5
4.解法描述
这个题目一看就和刚开始用插入排序链表的问题类似，只不过插入排序需要从小到大排序，而这里的分隔用了一个基准点来分隔链表。算法原理也类似，我这里是用一个新链表来存储当节点值大于等于x时候的节点，而原链表则存储比x小的节点，这里用链表的断开特性很好操作。具体代码如下：

public class Solution {
	public ListNode partition(ListNode head, int x) {
		 if (head == null || head.next == null)
				return head;
		 // l1存储>=x的，l2存储<x的
			ListNode l1 = new ListNode(0),l2=new ListNode(0);
			l2.next=head;
			ListNode pre=l2,temp = l2.next,temp_l1=l1;
	
			while (temp != null) {
				if (temp.val < x) {
					temp = temp.next;
					pre=pre.next;
				}else {
				//前节点的下一个节点位置重新链接，因此pre不需要移动
					temp_l1.next=temp;
					pre.next=temp.next;	
					
					temp=temp.next;
					temp_l1=temp_l1.next;
					temp_l1.next=null;	//断开
				}
			}
			//两个链表合并
			if(pre.next==null) {
				pre.next=l1.next;
			}else {
				pre.next.next=l1.next;
			}
			return l2.next;
	}
}

这样算法的时间复杂度是O(n)，只需要遍历一遍链表，空间复杂度为O(1)。