FilesExpand file tree

 master

/

LeetCode148.java

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

38 lines (36 loc) · 1.09 KB

 master

/

LeetCode148.java

Top

File metadata and controls

• Code
• Blame

38 lines (36 loc) · 1.09 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

package problems;

public class LeetCode148 {

public ListNode sortList(ListNode head) {

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

return head;

ListNode slow=head;

ListNode fast=head;

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

slow=slow.next;

fast=fast.next.next;

}

ListNode head2 = slow.next;

slow.next = null;

return merge(sortList(head), sortList(head2));

}

private ListNode merge(ListNode head1, ListNode head2) {

ListNode dummyHead = new ListNode(0);

ListNode temp = dummyHead, temp1 = head1, temp2 = head2;

while (temp1 != null && temp2 != null) {

if (temp1.val <= temp2.val) {

temp.next = temp1;

temp1 = temp1.next;

} else {

temp.next = temp2;

temp2 = temp2.next;

}

temp = temp.next;

}

if (temp1 != null) {

temp.next = temp1;

} else if (temp2 != null) {

temp.next = temp2;

}

return dummyHead.next;

}

}