Tag: linked list

LeetCode 160 Intersection of Two Linked Lists in Java

In this post I will be solving LeetCode 160 Intersection of Two Linked Lists using the Java programming language.

Given the heads of two singly linked-lists headA and headB, 
return the node at which the two lists intersect. 
If the two linked lists have no intersection at all, return null.

Custom Judge:

The inputs to the judge are given as follows (your program is not given these inputs):

o intersectVal - The value of the node where the intersection occurs.
  This is 0 if there is no intersected node.
o listA - The first linked list.
o listB - The second linked list.
o skipA - The number of nodes to skip ahead in listA (starting from the head) 
  to get to the intersected node.
o skipB - The number of nodes to skip ahead in listB (starting from the head) 
  to get to the intersected node.

The judge will then create the linked structure based on these inputs and pass the two heads, 
headA and headB to your program.
If you correctly return the intersected node,
then your solution will be accepted.

Constraints:

o The number of nodes of listA is in the m.
o The number of nodes of listB is in the n.
o 1 <= m, n <= 3 * 104
o 1 <= Node.val <= 105
o 0 <= skipA < m
o 0 <= skipB < n
o intersectVal is 0 if listA and listB do not intersect.
o intersectVal == listA[skipA] == listB[skipB] if listA and listB intersect.

Related Topics:

* Hash Table
o Linked List
* Two Pointers

Follow up:

* Could you write a solution that runs in O(m + n) time and use only O(1) memory?

If interested I suggest you get the current description from LeetCode before you start coding. Continue reading “LeetCode 160 Intersection of Two Linked Lists in Java”

Remove the Nth Node From End of List

Happy Friday! It is a typical fall Friday in the Twin Cities of Minneapolis and St. Paul. When I woke up this morning the outside temperature was 38F. The forecasted high for the day is 56F. Tomorrow the forecasted high temperature will be 67F. Will check with my wife if we will grill outside. Not too many grilling days left this year.

Earlier today I read the article Big whales eat 3 times as much as previously thought, which means killing them for food and blubber is even more harmful to the environment by Marianne Guenot. I also read a different article on the same subject titled The Enormous Hole That Whaling Left Behind by Ed Yong. Both articles are in agreement with the research and published papers. As humans, the idea of fertilizing the waters in specific areas seems to be a good thing to do now that the amounts of iron to use have been accurately estimated. Perhaps in the next few decades the oceans will see whales in the numbers they existed 60 years ago. Continue reading “Remove the Nth Node From End of List”

Flatten a Multilevel Doubly Linked List

Good morning software developers and software engineers! Hope your day has started on the right note. Every morning, weather allowing for it, my wife and I have breakfast and go for a brisk walk. Today was no exception. Before 08:00 AM I have watered plants in the yard including a rosemary bush that we planted a week ago or so, showered, shaved, got dressed and started my work day. It is amazing how well you feed during the day once you have exercised, no matter how short or long.

Last week I read the article (let me see if I can find it in my Twitter account @john_canessa … found it) Cybersecurity bills gain new urgency after rash of attacks. It seems that both political parties, Democrats and Republicans are pushing a bill that will help our country against cyber attacks. In the past few months we have seen hundreds if not thousands of attacks, some to disable our government, companies and organizations or to ask for ransom. One of the proposed ideas is to force targets to disclose in a short period of time (24 hours or so) any cyber breach they have experienced. This will allow the government and other organizations to take action as needed to prevent the same type of attacks. In my opinion there should be some type of penalty for the bad actors in an attempt to curb their proliferation (transparency and accountability). Will see what happens with the bill and its implementation! Continue reading “Flatten a Multilevel Doubly Linked List”

Flatten a Linked List in Java

This morning I read the article Kode Vicious Kabin Fever on Viewpoints in the latest copy of the Communications magazine from the ACM. I enjoyed reading the article. All of the points with the only exception to exercise, due to winter and the COVID-19 pandemic, with very few additions, are what I have been doing for over a decade. If you have time and are able to access the article, it contains good advice and it can be read in a few minutes.

Most problems in this blog come from companies such as HackerRank or LeetCode just to mention a few. In this case, the problem came up while chatting with a software engineer. I have developed the requirements as accurate as I can recall. I will be using the Java programming language on a Windows 10 machine using the VSCode IDE. Of course you can generate a solution in a different platform using a different IDE. Continue reading “Flatten a Linked List in Java”

Reverse Operations Revisited

Yesterday morning I attended a one hour webinar sponsored by the Association for Computing Machinery titled ACM Queue Case Study Q&A: Always-On Time-Series Database. It was very interesting. There was no presentation segment. There were only questions. The presenter, Theo Schlossnagle which is the founder of Circonus was very eloquent and seems very versed in the technology and their products.

During the conference I made several notes and searched for several topics that I found of interest. I will be reading the associated pages later this week. Continue reading “Reverse Operations Revisited”

Odd Even Linked List

Hi everybody! Hope you are doing well. It is Thursday evening and I do not know where the week went. We have one more day before the next weekend!

I was looking at singly linked lists in LeetCode and decided to tackle problem 328. Odd Even Linked List. If interested take a look at the requirements.

Given a singly linked list, 
group all odd nodes together followed by the even nodes. 
Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. 
The program should run in O(1) space complexity and O(nodes) time complexity.

Constraints:

o The relative order inside both the even and odd groups should remain as it was in the input.
o The first node is considered odd, the second node even and so on ...
o The length of the linked list is between [0, 10^4].

We are given a singly linked list and are asked to separate the nodes that are at odd indices from the ones at the even indices. The first node would be at position 1, the second node at position 2, the third note at position 3 and so on. The values in the node are of no interest. Continue reading “Odd Even Linked List”

Reverse Operations

In the past three days the high for the day has been in the mid to upper 40s. Since late fall a considerable amount of leaves has been accumulating in the entrance at home. Yesterday just before lunch I picked up the dead leaves. This morning some started to collect. I guess this is due to the orientation and shape of the entrance.

Last evening I also read an interesting article titled After Centuries, a Seemingly Simple Math Problem Gets an Exact Solution by Steve Nadis published in Quanta Magazine. Apparently a German mathematician named Ingo Ullisch figured out an exact solution for a problem. Good for him. What I liked more than the problem or its solution is the last paragraph in the article. In my humble opinion, this reaffirms the fact that reading and experimenting is the best way to learn. Continue reading “Reverse Operations”

Number of Recent Calls

It is an ugly rainy and stormy day in the Twin Cities of Minneapolis and St. Paul.  It seems like the storms will resume around 03:00 PM later today. In general I shutdown all my desktop computers when there are thunderstorms. I have a couple UPS units but I have also invested time installing software and configuring them exactly the way I like it. Do not wish to change disks or re install software.

Earlier today I opened the LeetCode web site and selected the problems icon. In the search box I entered the word “recursion”. Many problems were listed. I sorted them by difficulty Easy to Difficult. I then selected problem 933. Number of Recent Calls. Time permitting, decided to tackle three problems in the three categories in the next few days. Continue reading “Number of Recent Calls”

Java Collections List

It is a gloomy Tuesday in the Twin Cities of Minneapolis and St. Paul. It rained last night. It is quite damp. It is a typical fall day in this part of the country. The only difference is that in the past two years the lawns are green instead of being brown. I do not know for sure the cause for the climate change which is a very controversial topic, but for sure something is changing.

I am going to quickly cover some operations with Lists in Java. Will use lists on my next post. I need a refresher given that lately I have been working with C/C++ and after a few weeks (which in this case included a two week holiday) of not working with a programming language I tend to stumble with the syntax. It all gets back after a day or so of concentrating on the specific language. Continue reading “Java Collections List”

Circular Queue Using Linked List

It is Saturday October 12, 2019 in the Twin Cities of Minneapolis and St. Paul and we are receiving the first snowfall of the season. Seems like a couple days ago the temperature dropped 50 degrees F in a single day in Colorado producing a big snow storm. We are getting the remnants of it.

I took some days off and traveled with friends and family to Europe. We visited Rome, Naples, Sicily, Bruges and Amsterdam. The temperatures in Italy were in the 80s, while the weather in Belgium and the Netherlands was in the 40s and rainy. We saw, ate and had a great time. That said; it is good to be back home. Continue reading “Circular Queue Using Linked List”