DEV Community

Somuya Khandelwal
Somuya Khandelwal

Posted on

Day 5 of My Competitive Programming Journey: Unlocking the Power of Linked Lists

Hello Everyone!

I am Somuya Khandelwal and here to share the exciting progress I made on Day 5 of my competitive programming journey. After working through queues yesterday, today I ventured into the world of Linked Lists—one of the most fundamental yet versatile data structures in programming.

Linked lists may seem simple at first glance, but their flexibility and dynamic nature make them indispensable for solving a wide range of problems. My focus today was to strengthen my understanding of linked lists by solving three medium and two hard problems on Leetcode.

What I Worked On Today

  1. Reverse a Linked List (Medium Difficulty)

  2. This was a classic problem where a singly linked list needed to be reversed. I learned how to manipulate the pointers (prev, curr, and next) in order to reverse the links between nodes in an iterative manner. For extra challenge, I implemented the recursive approach, furthering my understanding of how stack-based recursion works for linked lists.

  3. Merge Two Sorted Linked Lists (Medium)
    To merge two sorted linked lists into a single list sorted, this was my task. With the aid of a dummy node to avoid dealing with lots of conditions to simplify the merging process, I compared the nodes one at a time from the two lists, thus bringing about an efficient merge.

  4. This problem taught me how to handle edge cases, which in this case included when one list was empty or significantly shorter than the other.

  5. Find the Middle of a Linked List (Medium Difficulty)
    This is a very straightforward yet insight-giving problem. One had to find the middle node of a linked list.

  6. Used two-pointer technique: Move the first pointer twice as fast as the second. This enables to search for the middle node on a single traversal.

  7. Find a Cycle in a Linked List (Complexity Difficulty)

    The problem: Determines whether there is a cycle in the linked list.

  8. I used Floyd's Tortoise and Hare algorithm to detect the presence of cycles in efficient ways by checking if two pointers, one moving at a faster pace than the other, ever met.

    • This algorithm taught me to manipulate pointers to solve the problems of linked lists.

  9. Flatten a Multilevel Doubly Linked List (Hard Difficulty)

  10. The problem was to flatten a multi-level doubly linked list into a single level list.

    • Using recursion, I went through each level connecting nodes while keeping the structure intact.
    • Debugging this problem made me appreciate the subtlety of pointer-based data structures.

What I Learned Today

  1. Pointer Manipulation:

  2. Handling linked lists demands a lot of care in handling the pointers. A small mistake leads to either null pointer exceptions or infinite loops, so a lot of care is necessary.

  3. Two-Pointer Technique:

    • This is a nice technique applied in finding the middle node and detecting cycle problems, which should be in the toolkit of any programmer.

  4. Recursive vs Iterative Solutions:
    -Sometimes, the trade-off for simplicity (recursion) versus efficiency (iteration) was evident in comparison, while trying to reverse a linked list using recursive and iterative methods.

  5. Use cases for practical scenarios:
    Linked lists- from dynamic memory allocation, implementing stacks and queues-the application of this data structure never ends. The problems encountered on today illustrate this nicely.

Day 5 was one both rewarding and challenging, though. It had its very trying Flatten a Multilevel Doubly Linked List problem in patience where debugging recursive pointer manipulation proved no small feat, but when finally working through, all effort becomes worth it.

Linked lists seem to be an academic topic but in solving these problems really depicted their application in the solving of real-world issues. The practical experience also improved my confidence in manipulating pointer-based data structures.

Now, at the end of my first week in competitive programming, I feel motivated to work harder. Next week I will look into the topic of Dynamic Programming-the powerful paradigm for unlocking solutions to some of the most complex algorithmic problems.

Thanks for being part of my journey so far! Hope my experiences inspire you to take on your own challenges and explore the limitless potential of problem-solving. Stay tuned for more updates as I continue to learn and grow.

Top comments (0)