April 1 - Daily Programming Diary

01.04.2021 — Diary, Programming — 1 min read

17:00

Wow, I've been inactive! Have put on some weight as well but motivated to start this again. It's a new month so let's go with Leetcode Question of the day. The question is to check whether the Linked List is a palindrome.

The first approach is to push everything in stack and then iterate over the list again to check if the reverse of the list matches with the original.

I've been rusty and I think the best way to reach that "follow up" to do it in O(n) time and O(1) space, is to first implement this approach and think what can be improved.

palindrome-linked-list-using-stack.cpp

1bool isPalindrome(ListNode *head) {
2    stack<int> s;
3    ListNode *temp = head;
4
5    while (temp) {
6        s.push(temp->val);
7        temp = temp->next;
8    }
9
10    while (head) {
11        if (s.top() != head->val)
12            return false;
13
14        s.pop();
15        head = head->next;
16    }
17
18    return true;
19}

The above method has time and space complexity both as O(n).

17:30

The next approach is to reverse the 2nd half of the list, and the check if both the halves are equal (barring the middle element in a list with odd elements).

palindrome-linked-list-using-reverse.cpp

1ListNode *reverseList(ListNode *head) {
2    ListNode *prev = NULL, *curr = head, *next = NULL;
3
4    while (curr) {
5        next = curr->next;
6        curr->next = prev;
7        prev = curr;
8        curr = next;
9    }
10
11    return prev;
12}
13
14bool isPalindrome(ListNode *head) {
15    ListNode *slow = head, *fast = head;
16    ListNode *mid = NULL;
17
18    // return true if only one node
19    if (head->next == NULL) return true;
20
21    while (fast && fast->next) {
22        fast = fast->next->next;
23        mid = slow;
24        slow = slow->next;
25    }
26
27    if (fast) slow = slow->next;
28
29    slow = reverseList(slow);
30
31    while (slow && head) {
32        if (slow->val != head->val) return false;
33        slow = slow->next;
34        head = head->next;
35    }
36
37    return true;
38}

The complexity of this approach is O(n) time and O(1) space.

EOD Checklist

Leetcode April Challenge
This blog