Given a singly linked list, determine if it is a palindrome.
A palindrome is a string/number that mirrors itself, for example, 21312 reverse is also 21312. We are given a linked list with 1 forward direction, we can convert the list to a vector, which has O(1) random access time compare to O(n) using linked list. However, a better approach is to push the node to a stack as it goes through the list. The second scan would be to compare the element from the stack with the node in the list.
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 | /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: bool isPalindrome(ListNode* head) { ListNode* p = head; stack<int> st; while (p != NULL) { st.push(p->val); // pushes to the stack p = p->next; } p = head; while (!st.empty()) { int x = st.top(); // first in last out st.pop(); if (p->val != x) { return false; } p = p->next; } return true; // stack empty } }; |
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head) {
ListNode* p = head;
stack<int> st;
while (p != NULL) {
st.push(p->val); // pushes to the stack
p = p->next;
}
p = head;
while (!st.empty()) {
int x = st.top(); // first in last out
st.pop();
if (p->val != x) {
return false;
}
p = p->next;
}
return true; // stack empty
}
};Because the stack implements First In Last Out, if all elements match, the linked list is a palindrome.
–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
loading...
248 wordsloading...
Last Post: How to Rotate Array in C/C++?
Next Post: Dynamic Programming - Perfect Squares