FilesExpand file tree

 master

/

Solution42.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

88 lines (86 loc) · 2.01 KB

 master

/

Solution42.java

Copy path

Top

File metadata and controls

• Code
• Blame

88 lines (86 loc) · 2.01 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

import java.util.ArrayList;

/*

* Reorder List

* Given a singly linked list L: L0¡úL1¡ú¡­¡úLn-1¡úLn

* reorder it to: L0¡úLn¡úL1¡úLn-1¡úL2¡úLn-2¡ú¡­

*/

public class Solution42 {

static class ListNode {

int val;

ListNode next;

ListNode(int x) {

val = x;

next = null;

}

}

public void reorderList(ListNode head) {

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

ArrayList<ListNode> record = new ArrayList<ListNode>();

ListNode cur = head;

while (cur != null) {

record.add(cur);

cur = cur.next;

}

int len = record.size();

int i =0, j = len - 1;

while (i != j && j-i != 1) {

record.get(i).next = record.get(j);

record.get(j).next = record.get(i+1);

i++;

j--;

}

if (i == j)

record.get(i).next = null;

else {

record.get(i).next = record.get(j);

record.get(j).next = null;

}

}

/*same val node runtime error

public void reorderList(ListNode head) {

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

ListNode node = null;

ListNode next = head.next;

ListNode cur = new ListNode(head.val);

ListNode curNode = cur;

while (next != null) {

cur.next = new ListNode(next.val);

cur = cur.next;

next = next.next;

}

while (curNode != null) {

ListNode temp = curNode.next;

curNode.next = node;

node = curNode;

curNode = temp;

}

cur = head;

while (cur.val != node.val && cur.next.val != node.val) {

ListNode temp1 = cur.next;

ListNode temp2 = node.next;

cur.next = node;

node.next = temp1;

cur = temp1;

node = temp2;

}

if (cur.val == node.val)

cur.next = null;

else {

cur.next = node;

cur.next.next = null;

}

}*/

public static void main(String ...args) {

Solution42 s42 = new Solution42();

ListNode head = new ListNode(1);

head.next = new ListNode(2);

head.next.next = new ListNode(3);

head.next.next.next = new ListNode(4);

s42.reorderList(head);

while (head != null) {

System.out.print(head.val + " ");

head = head.next;

}

System.out.println();

}

}