LeetCode Sort List

題意：給定一個list的節點，對它進行排序

解法：歸并排序咯~直接上碼

<span style="font-size:18px;">class ListNode {
	int val;
	ListNode next;

	ListNode(int x) {
		val = x;
		next = null;
	}
}

public class Solution {
	public ListNode sortList(ListNode head) {
		if (head == null || head.next == null)
			return head;
		ListNode h1 = head;
		int len = 0;
		ListNode t1 = h1, t2;
		while (t1 != null) {
			len++;
			t1 = t1.next;
		}
		if (len == 0 || len == 1) {

			return h1;
		}
		t1 = h1;
		for (int i = 1; i < len / 2; i++)
			t1 = t1.next;
		ListNode h2 = t1.next;
		t1.next = null;
		h1 = sortList(h1);
		h2 = sortList(h2);

		t1 = h1;
		t2 = h2;
		ListNode current;
		if (t1.val < t2.val) {
			head = t1;
			t1 = t1.next;
		} else {
			head = t2;
			t2 = t2.next;
		}
		current = head;

		while (t1 != null && t2 != null) {
			if (t1.val < t2.val) {
				current.next = t1;
				current = current.next;
				t1 = t1.next;
			} else {
				current.next = t2;
				current = current.next;
				t2 = t2.next;
			}
		}

		if (t1 != null) {
			current.next = t1;
		} else {
			current.next = t2;
		}
		return head;
	}

	public static void main(String[] args) {
		ListNode h1 = new ListNode(20);
		ListNode h2 = new ListNode(5);
		ListNode h3 = new ListNode(4);
		ListNode h4 = new ListNode(1);
		ListNode h5 = new ListNode(3);
		h1.next = h2;
		h2.next = h3;
		h3.next = h4;
		h4.next = h5;
		Solution s = new Solution();
		ListNode h = s.sortList(h1);
		s.print(h);
	}

	public void print(ListNode h) {
		while (h != null) {
			System.out.print(h.val + "   ");
			h = h.next;
		}
		System.out.println();
	}
}</span>