FilesExpand file tree

 master

/

SortList_leetCode.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

79 lines (63 loc) · 1.76 KB

 master

/

SortList_leetCode.java

Copy path

Top

File metadata and controls

• Code
• Blame

79 lines (63 loc) · 1.76 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

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

package Algorithms.sort;

import Algorithms.algorithm.others.ListNode;

/**

* Definition for singly-linked list.

* class ListNode {

* int val;

* ListNode next;

* ListNode(int x) {

* val = x;

* next = null;

* }

* }

*/

public class SortList_leetCode {

public ListNode sortList(ListNode head) {

if (head == null) {

return null;

}

// !! Remember to add this line! Because this may cause infinit loop.

if (head.next == null) {

return head;

}

ListNode midPre = findmidPre(head);

ListNode right = sortList(midPre.next);

midPre.next = null;

ListNode left = sortList(head);

return merge(left, right);

}

// get the node before mid.

public ListNode findmidPre(ListNode head) {

if (head == null) {

return null;

}

ListNode slow = head;

ListNode fast = head.next;

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

fast = fast.next.next;

slow = slow.next;

}

return slow;

}

// get the node before mid.

public ListNode merge(ListNode h1, ListNode h2) {

ListNode dummy = new ListNode(0);

ListNode cur = dummy;

while (h1 != null && h2 != null) {

if (h1.val < h2.val) {

cur.next = h1;

h1 = h1.next;

} else {

cur.next = h2;

h2 = h2.next;

}

cur = cur.next;

}

if (h1 != null) {

cur.next = h1;

} else {

cur.next = h2;

}

return dummy.next;

}

}