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