Commit28021f4

applewjg

committed

Sort List

Change-Id: I18bf4e8a53e674bad76f1a21a4624580aebc1c4e

1 parent424fcb8 commit28021f4Copy full SHA for 28021f4

File tree

+54

-0

lines changed

+54

-0

lines changed

Lines changed: 54 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,54 @@`
	`1`	`+/*`
	`2`	`+ Author: King, wangjingui@outlook.com`
	`3`	`+ Date: Jan 2, 2015`
	`4`	`+ Problem: Sort List`
	`5`	`+ Difficulty: Medium`
	`6`	`+ Source: http://oj.leetcode.com/problems/sort-list/`
	`7`	`+ Notes:`
	`8`	`+ Sort a linked list in O(nlogn) time using constant space complexity.`
	`9`	`+`
	`10`	`+ Solution: merge sort.`
	`11`	`+ */`
	`12`	`+/**`
	`13`	`+ * Definition for singly-linked list.`
	`14`	`+ * class ListNode {`
	`15`	`+ * int val;`
	`16`	`+ * ListNode next;`
	`17`	`+ * ListNode(int x) {`
	`18`	`+ * val = x;`
	`19`	`+ * next = null;`
	`20`	`+ * }`
	`21`	`+ * }`
	`22`	`+ */`
	`23`	`+publicclassSolution {`
	`24`	`+publicListNodesortList(ListNodehead) {`
	`25`	`+if (head ==null \|\|head.next ==null)returnhead;`
	`26`	`+ListNodeslow =head,fast =head;`
	`27`	`+while (fast.next !=null &&fast.next.next !=null) {`
	`28`	`+fast =fast.next.next;`
	`29`	`+slow =slow.next;`
	`30`	`+ }`
	`31`	`+fast =slow.next;`
	`32`	`+slow.next =null;`
	`33`	`+ListNodel1 =sortList(head);`
	`34`	`+ListNodel2 =sortList(fast);`
	`35`	`+returnmergeTwoLists(l1,l2);`
	`36`	`+ }`
	`37`	`+publicListNodemergeTwoLists(ListNodel1,ListNodel2) {`
	`38`	`+ListNodehead =newListNode(0);`
	`39`	`+ListNodecur =head;`
	`40`	`+while (l1 !=null &&l2 !=null) {`
	`41`	`+if (l1.val <l2.val) {`
	`42`	`+cur.next =l1;`
	`43`	`+l1 =l1.next;`
	`44`	`+ }else {`
	`45`	`+cur.next =l2;`
	`46`	`+l2 =l2.next;`
	`47`	`+ }`
	`48`	`+cur =cur.next;`
	`49`	`+ }`
	`50`	`+if (l1 !=null)cur.next =l1;`
	`51`	`+if (l2 !=null)cur.next =l2;`
	`52`	`+returnhead.next;`
	`53`	`+ }`
	`54`	`+}`

Comments

(0)