[LeetCode] 234. Palindrome Linked List

轉自LeetCode

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?

<Solution>

解提想法如下

• 利用快慢指標來找到中間點

• 把後半部反轉

• 逐一檢查前半部和後半部的元素，是否都相同

code 如下

C++
Java

還有一種解法，可以借用 stack

先把 node 都放到 stack 裡面，然後只要拿出後半部，逐一比對即可

因為 stack 是 FILO 的結構，所以剛好會用反過來的順序拿出 node

kotlin