DEV Community

Ertugrul
Ertugrul

Posted on

πŸ—“ Daily LeetCode Progress – Day 18

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
Enter fullscreen mode Exit fullscreen mode

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;
    }
};
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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);
    }
};
Enter fullscreen mode Exit fullscreen mode

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++.

Imp python

Imp cpp

  • Computed binary tree diameter via DFS height calculation in both languages.

btd python

btd cpp


πŸ“¦ 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

Top comments (0)