FilesExpand file tree

 main

/

LeetCode234.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

61 lines (57 loc) · 1.63 KB

 main

/

LeetCode234.java

Copy path

Top

File metadata and controls

• Code
• Blame

61 lines (57 loc) · 1.63 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

package com.xxx;

import java.util.ArrayList;

import java.util.List;

public class LeetCode234 {

// O(n) 空间复杂度

public boolean isPalindrome1(ListNode head) {

// 用数组存储链表的值

List<Integer> values = new ArrayList<>();

ListNode current = head;

while (current != null) {

values.add(current.val);

current = current.next;

}

// 用双指针判断是否是回文

int left = 0;

int right = values.size() - 1;

while (left < right) {

if (!values.get(left).equals(values.get(right))) {

return false;

}

left++;

right--;

}

return true;

}

// O(n) 时间复杂度 + O(1) 空间复杂度

public boolean isPalindrome2(ListNode head) {

ListNode fast = head;

ListNode slow = head;

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

fast = fast.next.next;

slow = slow.next;

}

fast = head;

slow = transListNode(slow);

while (slow != null) {

if (fast.val != slow.val) {

return false;

}

fast = fast.next;

slow = slow.next;

}

return true;

}

// 翻转链表

public ListNode transListNode(ListNode head) {

ListNode pre = null;

ListNode node = head;

while (node != null) {

ListNode temp = node.next;

node.next = pre;

pre = node;

node = temp;

}

return pre;

}

}