刷題日記（1）Palindrome Linked List

Palindrome Linked List

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

Example 1:

Input: 1->2

Output: false

Example 2:

Input: 1->2->2->1

Output: true

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

以這個作為舉例

解題思路

1. 找中間

2.反轉後半

3.相比從頭尾開始

4.p2為null 則true

(main function)

1. 從main function開始, 判斷如果傳進來的list node為null, 則return true;

2. 設一個名字middle node呼叫find middle function 去找到middle

(find middle function)

3. Slow 等於head, Fast 等於slow的next (雙指針)

4. 當fast和fast的next不為null時, 則slow 進一步, fast進兩步 以此類推,接下來slow和fast會越差越多格（差1格,差2格,差3格….）,直到fast的next為null表示fast來到最後

5. 此時slow在中間,回傳slow

(main function)

6. 得到middle等於slow的位置後, 必須反轉中間以後的鏈表位置

7. middle 的next 等於呼叫reverse function得到的結果, 傳入原本的middle next, 最後middle 的next會連結到原本後半鏈表的最後一個（已經反轉過來了）

(reverse function)

8. 先設一個Node prev等於null (等等後面用)

9. 當head不為null時,

9.1 head的next等於temp (先標記以免等下消失)

9.2 然後head的next指到prev

9.3 然後把prev的標籤移到head頭上

9.4 然後head的標籤移到temp頭上

10. 最後當head為null時, 表示prev為null的前一個（已經在最後了）,所以傳回去prev給原本的middle的next, 此時鏈表的後半段已經反過來了

(main function)

11. 得到中間和反轉的鏈表後, 先assign p1標籤給原本鏈表的頭, 再assign p2標籤給middle next（就是原本鏈表的最後一個node,但因為已經反轉, 所以他在middle next了）

12. 開始相比p1 和 p2, 當p1 和p2 不為null且p1和p2值相等時,

12.1 p1等於p1.next

12.2 然後p2等於p2.next

13. 最後如果p2等於null的話 則成立, 因為middle 在p1的part所以不管如何p2最終只能是null

參考用