Problems Solved:
- #83 Remove Duplicates from Sorted List
- #202 Happy Number
This continues my daily series (Day 15: Linked List + Hashing patterns). Hitting a 15βday streak π feels especially rewarding β these milestone days (5/10/15) keep me pushing forward and highlight consistency over half a month of practice.
π‘ What I Learned
Todayβs focus was on linked list traversal and cycle detection via hashing:
- For Remove Duplicates from Sorted List, I practiced inβplace modification of a sorted linked list. The trick is to compare the current node with its next, and if equal, bypass the duplicate by rewiring the pointer. This way, we only walk the list once.
- For Happy Number, I reinforced the idea of detecting cycles in number transformations. Using a hash set (
seen
) to remember previously visited numbers ensures that if the process loops endlessly, we stop. Itβs conceptually similar to cycle detection in linked lists.
π§© #83 β Remove Duplicates from Sorted List
Python (Pointer skip)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
cur = head
while cur and cur.next:
if cur.val == cur.next.val:
cur.next = cur.next.next
else:
cur = cur.next
return head
Why it works: In a sorted list, duplicates are adjacent. By skipping cur.next
whenever it matches cur.val
, we remove duplicates on the fly.
Time: O(n)
(one pass)
Space: O(1)
(no extra data structures)
C++ (Safe pointer update)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode* cur = head;
while (cur != nullptr && cur->next != nullptr) {
if (cur->val == cur->next->val) {
cur->next = cur->next->next;
} else {
cur = cur->next;
}
}
return head;
}
};
Why it works: Identical pointer logic as Python. Always check cur
and cur->next
to avoid null dereference.
Time: O(n)
Space: O(1)
π§© #202 β Happy Number
Python (Hash set for cycle detection)
class Solution:
def isHappy(self, n: int) -> bool:
seen = set()
while n != 1 and n not in seen:
seen.add(n)
n = sum(int(d)**2 for d in str(n))
return n == 1
Why it works: Each step transforms the number into the sum of digit squares. If we ever repeat a number (seen
), weβre stuck in a cycle. Only breaking condition: reaching 1
.
Time: O(k)
where k
is the length of the cycle + path
Space: O(k)
for the set
C++ (Helper for digitβsquares)
class Solution {
public:
bool isHappy(int n) {
unordered_set<int> seen;
while (n != 1 && seen.find(n) == seen.end()) {
seen.insert(n);
n = nextNumber(n);
}
return n == 1;
}
private:
int nextNumber(int n) {
int total = 0;
while (n > 0) {
int digit = n % 10;
total += digit * digit;
n /= 10;
}
return total;
}
};
Why it works: Same as Python. unordered_set
ensures cycle detection. nextNumber
computes the digit square sum cleanly.
Time: O(k)
Space: O(k)
πΈ Achievements
- Remove Duplicates from Sorted List: Solidified pointer manipulation in both Python and C++. Avoiding nullβpointer pitfalls was key.
- Happy Number: Understood how cycle detection via sets mirrors linked list cycle detection. Python and C++ implementations verified.
π¦ Complexity Recap
-
Remove Duplicates from Sorted List:
O(n)
time,O(1)
space. -
Happy Number:
O(k)
time,O(k)
space (can be optimized toO(1)
with Floydβs cycle detection).
π£ Join the Journey
Day 15 streak π₯ achieved! Solving problems daily for over two weeks has been a rewarding challenge. Every 5βday checkpoint strengthens the habit and showcases progress.
Follow along if youβre interested in algorithms, patterns, and writing clean solutions in both Python and C++.
Links
- LinkedIn: https://www.linkedin.com/in/ertugrul-mutlu
- GitHub Series: https://github.com/Ertugrulmutlu/leetcode-series
Top comments (0)