[LeetCode] Palindrome Linked List

更新时间：2022-06-09 19:26:50

The idea is not so obvious at first glance. Since you cannot move from a node back to its previous node in a singly linked list, we choose to reverse the right half of the list and then compare it with the left half. The code is as follows. It shoul be obvious after you run some examples.

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     bool isPalindrome(ListNode* head) {
12         if (!head || !(head -> next)) return true;
13         ListNode* slow = head;
14         ListNode* fast = head;
15         while (fast && fast -> next) {
16             slow = slow -> next;
17             fast = fast -> next -> next;
18         }
19         if (fast) {
20             slow -> next = reverseList(slow -> next);
21             slow = slow -> next;
22         }
23         else slow = reverseList(slow);
24         while (slow) {
25             if (head -> val != slow -> val)
26                 return false;
27             head = head -> next;
28             slow = slow -> next;
29         }
30         return true;
31     }
32 private:
33     ListNode* reverseList(ListNode* node) {
34         ListNode* pre = NULL;
35         while (node) {
36             ListNode* next = node -> next;
37             node -> next = pre;
38             pre = node;
39             node = next;
40         }
41         return pre;
42     }
43 };

上一篇 : ：[LeetCode] Lowest Common Ancestor of a Binary Search Tree下一篇 : [LeetCode] Binary Search Tree Iterator

[LeetCode] Palindrome Linked List

相关阅读

推荐文章