FilesExpand file tree

 master

/

148_sortList.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

59 lines (57 loc) · 1.63 KB

 master

/

148_sortList.java

Copy path

Top

File metadata and controls

• Code
• Blame

59 lines (57 loc) · 1.63 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

/**

* Definition for singly-linked list.

* public class ListNode {

* int val;

* ListNode next;

* ListNode() {}

* ListNode(int val) { this.val = val; }

* ListNode(int val, ListNode next) { this.val = val; this.next = next; }

* }

*/

class Solution {

public ListNode sortList(ListNode head) {

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

ListNode[] nodes = split(head);

ListNode l = sortList(nodes[0]);

ListNode r = sortList(nodes[1]);

return merge(l,r);

}

public ListNode[] split(ListNode head){

ListNode dummy = new ListNode(0);

dummy.next = head; //Add dummy in front to make sure slow would be the mid!

ListNode fast = dummy;

ListNode slow = dummy;

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

fast = fast.next.next;

slow = slow.next;

}

ListNode r = slow.next;

ListNode l = dummy.next;

slow.next = null;

ListNode[] res = new ListNode[2];

res[0] = l;

res[1] = r;

return res;

}

public ListNode merge(ListNode l, ListNode r){

ListNode dummy = new ListNode(0);

ListNode run = dummy;

while(l != null && r != null){

if(l.val < r.val){

run.next = new ListNode(l.val);

l = l.next;

} else{

run.next = new ListNode(r.val);

r = r.next;

}

run = run.next;

}

if(l != null){

run.next = l;

}

if(r != null){

run.next = r;

}

return dummy.next;

}

}