Problems Solved:
- #160 Intersection of Two Linked Lists
- #543 Diameter of Binary Tree
This continues my daily series (Day 18: Linked List Intersection + Tree Diameter). Today I worked on two fundamental data structure problems: finding the intersection node of two singly linked lists, and computing the diameter of a binary tree.
π‘ What I Learned
- For Intersection of Two Linked Lists, the key idea is that if we traverse both lists with two pointers and switch heads after reaching the end, both pointers will cover the same total distance. They eventually meet at the intersection node or at
null
if there is no intersection. - For Diameter of Binary Tree, the longest path between two nodes is the sum of the heights of the left and right subtrees at some node. Using DFS, we can compute subtree heights while updating a global maximum diameter.
- Both problems reinforce the utility of two-pointer traversal and depth-first recursion for linked list and tree tasks.
π§© #160 β Intersection of Two Linked Lists
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
a, b = headA, headB
while a is not b:
a = a.next if a else headB
b = b.next if b else headA
return a
C++
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if (!headA || !headB) return nullptr;
ListNode *a = headA;
ListNode *b = headB;
while (a != b) {
a = (a == nullptr) ? headB : a->next;
b = (b == nullptr) ? headA : b->next;
}
return a;
}
};
Time: O(m + n)
Space: O(1)
π§© #543 β Diameter of Binary Tree
Python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
self.diameter = 0
def dfs(node):
if not node:
return 0
left_height = dfs(node.left)
right_height = dfs(node.right)
self.diameter = max(self.diameter, left_height + right_height)
return 1 + max(left_height, right_height)
dfs(root)
return self.diameter
C++
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int diameterOfBinaryTree(TreeNode* root) {
int diameter = 0;
dfs(root, diameter);
return diameter;
}
private:
int dfs(TreeNode* node, int& diameter) {
if (!node) return 0;
int left = dfs(node->left, diameter);
int right = dfs(node->right, diameter);
diameter = max(diameter, left + right);
return 1 + max(left, right);
}
};
Time: O(n)
Space: O(h)
recursion stack, where h
is tree height.
πΈ Achievements
- Implemented a clean two-pointer approach for linked list intersection in both Python and C++.
- Computed binary tree diameter via DFS height calculation in both languages.
π¦ Complexity Recap
-
Intersection of Two Linked Lists:
O(m + n)
time,O(1)
space. -
Diameter of Binary Tree:
O(n)
time,O(h)
space.
π£ Join the Journey
Iβm solving and documenting problems daily in both Python and C++, covering arrays, linked lists, dynamic programming, and more. Follow along if youβre interested in systematic problem solving.
Links
- LinkedIn: https://www.linkedin.com/in/ertugrul-mutlu
- GitHub Series: https://github.com/Ertugrulmutlu/leetcode-series
Top comments (0)