leetCode 234. Palindrome Linked List 链表

234. Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

Follow up:

Could you do it in O(n) time and O(1) space?

题目大意：

判断一个单链表是否为回文链表。

思路：

找到链表中间的节点，将链表从中间分为2部分，右半部分进行链表反向转换，然后左半部分和反转后的右半部分链表进行比较。得出结果。

代码如下：

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

<code>/**</code>

<code> </code><code>* Definition for singly-linked list.</code>

<code> </code><code>* struct ListNode {</code>

<code> </code><code>*     int val;</code>

<code> </code><code>*     ListNode *next;</code>

<code> </code><code>*     ListNode(int x) : val(x), next(NULL) {}</code>

<code> </code><code>* };</code>

<code> </code><code>*/</code>

<code>class</code> <code>Solution {</code>

<code>public</code><code>:</code>

<code>    </code><code>ListNode * reverseList(ListNode *head) </code><code>//链表反转</code>

<code>    </code><code>{</code>

<code>        </code><code>ListNode *pre,*next;</code>

<code>        </code><code>pre = NULL;</code>

<code>        </code><code>next = NULL;</code>

<code>        </code> 

<code>        </code><code>while</code><code>(head)</code>

<code>        </code><code>{</code>

<code>            </code><code>next = head-&gt;next;</code>

<code>            </code><code>head-&gt;next = pre;</code>

<code>            </code><code>pre = head;</code>

<code>            </code><code>head = next;</code>

<code>        </code><code>}</code>

<code>        </code><code>return</code> <code>pre;</code>

<code>    </code><code>}</code>

<code>    </code><code>bool</code> <code>isPalindrome(ListNode* head) {</code>

<code>        </code><code>if</code><code>( NULL == head || NULL == head-&gt;next)</code>

<code>            </code><code>return</code> <code>true</code><code>;</code>

<code>        </code><code>int</code> <code>len = 0;</code>

<code>        </code><code>ListNode *p = head;</code>

<code>        </code><code>while</code><code>(p)</code>

<code>            </code><code>len++;</code>

<code>            </code><code>p = p-&gt;next;</code>

<code>        </code><code>ListNode * rightListHead;</code>

<code>        </code><code>rightListHead = head;</code>

<code>        </code><code>int</code> <code>leftLen = len / 2;</code>

<code>        </code><code>int</code> <code>rightLen = len - leftLen;</code>

<code>        </code><code>int</code> <code>i = leftLen;</code>

<code>        </code><code>while</code><code>(i)</code>

<code>            </code><code>rightListHead = rightListHead-&gt;next;</code>

<code>            </code><code>i--;</code>

<code>        </code><code>rightListHead = reverseList(rightListHead);</code>

<code>        </code><code>ListNode * left = head;</code>

<code>        </code><code>ListNode * right = rightListHead;</code>

<code>        </code><code>while</code><code>(i &lt; leftLen)</code>

<code>            </code><code>if</code><code>(left-&gt;val == right-&gt;val)</code>

<code>            </code><code>{</code>

<code>                </code><code>left = left-&gt;next;</code>

<code>                </code><code>right = right-&gt;next;</code>

<code>            </code><code>}</code>

<code>            </code><code>else</code>

<code>                </code><code>return</code> <code>false</code><code>;</code>

<code>            </code><code>i++;</code>

<code>        </code><code>return</code> <code>true</code><code>;</code>

<code>};</code>

复习了单链表反转的方法。

本文转自313119992 51CTO博客，原文链接:http://blog.51cto.com/qiaopeng688/1837428