FilesExpand file tree

 master

/

LeetCode234.java

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

49 lines (45 loc) · 1.34 KB

 master

/

LeetCode234.java

Top

File metadata and controls

• Code
• Blame

49 lines (45 loc) · 1.34 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

package problems;

public class LeetCode234 {

public boolean isPalindrome(ListNode head) {

if(head == null) {

return true;

}

// 找到前半部分链表的尾节点并反转后半部分链表

ListNode firstHalfEnd = endOfFirstHalf(head);

ListNode secondHalfStart = reverseList(firstHalfEnd.next);

// 判断是否回文

ListNode p1 = head;

ListNode p2 = secondHalfStart;

boolean result = true;

while (result && p2 != null) {

if (p1.val != p2.val) {

result = false;

}

p1 = p1.next;

p2 = p2.next;

}

// 还原链表并返回结果

firstHalfEnd.next = reverseList(secondHalfStart);

return result;

}

private ListNode reverseList(ListNode head) {

ListNode prev = null;

ListNode curr = head;

while (curr != null) {

ListNode nextTemp = curr.next;

curr.next = prev;

prev = curr;

curr = nextTemp;

}

return prev;

}

private ListNode endOfFirstHalf(ListNode head) {

ListNode fast = head;

ListNode slow = head;

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

fast = fast.next.next;

slow = slow.next;

}

return slow;

}

}