FilesExpand file tree

 master

/

SortListTest.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

60 lines (53 loc) · 1.14 KB

 master

/

SortListTest.java

Copy path

Top

File metadata and controls

• Code
• Blame

60 lines (53 loc) · 1.14 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

60

package leetcode;

public class SortListTest {

public static void main(String[] args) {

SortListTest test = new SortListTest();

ListNode l = new ListNode(4);

l.next = new ListNode(3);

l.next.next = new ListNode(1);

ListNode re= test.sortList(l);

System.out.println(re.val);

}

public ListNode sortList(ListNode head) {

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

ListNode fast = head;

ListNode slow = head;

ListNode prev= null;

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

prev=slow;

fast= fast.next.next;

slow= slow.next;

}

prev.next=null;

ListNode l1 = sortList(head);

ListNode l2 = sortList(slow);

return merge(l1,l2);

}

public ListNode merge(ListNode l1, ListNode l2){

ListNode result = new ListNode(0);

ListNode l= result;

while(l1!=null && l2!=null){

if(l1.val < l2.val){

l.next = l1;

l1= l1.next;

}

else{

l.next = l2;

l2= l2.next;

}

l= l.next;

}

if(l1!=null)

l.next= l1;

if(l2!=null)

l.next = l2;

return result.next;

}

}

/*class ListNode{

int val;

ListNode next;

ListNode(int x){

val=x;

}

}*/