FilesExpand file tree

 master

/

PartitionList86.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

104 lines (88 loc) · 2.66 KB

 master

/

PartitionList86.java

Copy path

Top

File metadata and controls

• Code
• Blame

104 lines (88 loc) · 2.66 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

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

/**

* Given a linked list and a value x, partition it such that all nodes less

* than x come before nodes greater than or equal to x.

*

* You should preserve the original relative order of the nodes in each of the two partitions.

*

* For example,

* Given 1->4->3->2->5->2 and x = 3,

* return 1->2->2->4->3->5.

*/

/**

* Definition for singly-linked list.

* public class ListNode {

* int val;

* ListNode next;

* ListNode(int x) { val = x; }

* }

*/

public class PartitionList86 {

public ListNode partition(ListNode head, int x) {

if (head == null) {

return null;

}

ListNode left = null;

ListNode leftEnd = null;

ListNode right = null;

ListNode rightEnd = null;

while (head != null) {

if (head.val < x) {

if (left == null) {

left = new ListNode(head.val);

} else if (leftEnd == null) {

leftEnd = new ListNode(head.val);

left.next = leftEnd;

} else {

leftEnd.next = new ListNode(head.val);

leftEnd = leftEnd.next;

}

} else {

if (right == null) {

right = new ListNode(head.val);

} else if (rightEnd == null) {

rightEnd = new ListNode(head.val);

right.next = rightEnd;

} else {

rightEnd.next = new ListNode(head.val);

rightEnd = rightEnd.next;

}

}

head = head.next;

}

if (leftEnd != null){

leftEnd.next = right;

return left;

} else if (left != null) {

left.next = right;

return left;

} else {

return right;

}

}

/**

* https://discuss.leetcode.com/topic/23951/java-solution-pick-out-larger-nodes-and-append-to-the-end

*/

public ListNode partition(ListNode head, int x) {

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

ListNode l1 = new ListNode(0);

ListNode l2 = new ListNode(0);

ListNode p1=l1, p2=l2;

p1.next = head;

while(p1.next!=null) {

// keep moving larger node to list 2;

if(p1.next.val>=x) {

ListNode tmp = p1.next;

p1.next = tmp.next;

p2.next = tmp;

p2 = p2.next;

}

else {

p1 = p1.next;

}

}

// conbine lists 1 and 2;

p2.next = null;

p1.next = l2.next;

return l1.next;

}

}