Converging linked lists

– Write the code in java please and please read below for better understanding.

– if you could implement the solution using object-oriented programming I will appreciate it. Correct object-oriented solutions will be awarded an added 50% bonus.

I will import the example files for you.

Below is the assignment:

Problem description

Assume that we have two singly linked lists of unknown length (i.e., number of nodes in each list). The lengths of the lists can be different (e.g., one list can have 8 notes and the other 5 nodes). The two lists converge into the first node of a singly linked list. This configuration is also equivalent to the “next” of the end node of one list to be linked to some in-between node of the other list. Once the two-headed list is constructed, the location of the convergence node is assumed to be unknown. Finding the convergence node is our main goal. The head nodes of each of the two converging lists are known. Figure 1 shows how the lists are linked.

Figure 1: Two lists that merge at a node. This node’s address is unknown, i.e., the function that finds the convergence node cannot use any information about that node. The only information provided to the function that finds the convergence node are the heads of the two-headed list.

Solution

A possible solution to this problem is as follows.

1. Create two stacks: one for the first list and one for the second list.
2. Traverse the first list and push all the node addresses onto the first stack.
3. Traverse the second list and push all the node addresses onto the second stack.
4. Now both stacks contain the node address of the corresponding lists.
5. Now compare the top node address of both stacks.
6. If they are the same, take the top elements from both the stacks and keep them in some temporary variable (since both node addresses are node, it is enough if we use one temporary variable).
7. Continue this process until the top node addresses of the stacks are not the same.
8. This point is the one where the lists merge into a single list.
9. Return the value of the temporary variable.

Assignment

Implement the solution described in the above algorithm. You must implement your own singly linked list, and stack. To create the linked lists in this assignment, you only need to implement functions to add nodes to the head and remove nodes from the head. These two functions will be useful for creating the lists and also for maintaining the two stacks. Your stacks should be implemented based on the list that you create (i.e., use the linked list as the basis for implementing the stack). Here, you do not need to use sentinels. Sentinels are useful if you are adding (or removing) nodes in places other than the head. In this assignment, you only adding (removing) nodes from the head of the lists (and stacks).

You can implement the solution using either standard programming or object-oriented programming. Correct object-oriented solutions will be awarded an added 50% bonus. There is no penalty for writing non-object oriented solutions. The bonus is only meant as an incentive. You are free to use the example list that I wrote in the lectures as a starter code for your implementation.

The stack in your program should use a linked list as its base implementation. The stack has two functions: push() and pop(). These two functions can be implemented by using the list functions addToHead() and removeFromHead(). These names are only suggestions. You are free to choose the name of these functions and their signatures.

Note: Based, on this description alone, you will design and write your own algorithm. Do not copy a solution from any source. Create your own solution and write your own code. Again, you are free to consult sources on C/C++ (Or Java) programming issues but you are not allowed to consult on the specific problem at hand. Again, in the case of this assignment, I do not care if your solution is ugly or if it efficient code or great code. What I care is that whatever you submit is own your solution, and that the solution works (of course!).

Graphical representation of the assignment

The following file is a graphical representation of the assignment, and its solution:

assignmentTwoPaths.pdf

What to submit (Canvas dropbox).

1. Submit your program’s source code (not the compiled executable or object files) as a single file.
2. Submit a screenshot (i.e., image file) of your program executing (e.g., png, jpg, gif, tiff). Points will be deducted for all submissions that do not follow the instructions (e.g., missing screenshot).
3. Your program should be self-contained. It should have a clear test program that creates the two-headed lists and calls the function that finds (and prints out) the intersection node. To grade your assignment, we will run your test program (make sure it works). Write a clear example on how we can run your program.

Further notes and comments

• The goal of the program is to locate the node where the lists intersect. It must do that without knowing the lengths of the lists. Your program should print the addresses (or numerical labels that identify the nodes) of all notes in the lists and then highlight the address of the detected intersection node. You are free to choose the way you will display this information.
• Your findIntersectionNode() function (if that is how you decide to call it) will not use information about the length of the lists or the actual location of the intersection node. Otherwise, the solution is trivial.
• There are only two lists, not three. From the diagram in Figure 1, we can say that List 1 merges with List 2 or that List 2 merges into List 1. These two cases are indistinguishable.
• The lists have no tail pointer. They only have head pointers. In the diagram in Figure 1, the head pointers are called List1 and List2. These two variables hold the address of the first node of the lists. If you want, you can have tail pointers. But, your function to find the intersection node cannot use the information from the tail pointers.
• The values to be stored in the nodes play no role in this assignment. You can simply set the values to something like 1, 2, 3,… Number-Of-Nodes.
• You will decide where the links merge. Of course, you will know where they connect because you will design the layout of the lists. But, your function to find the intersection node won’t know where the merging occurs. The task of your program is to find that node (where the merge happens) and print its address (or numerical label).
• The lists can have any size. As a result, any of the lists can be shorter or longer. They can also be of the same size.
• The algorithm above suggests that you save the addresses of nodes in a temporary variable as you compare them with the ones in the stack. Of course, if you are writing the program in C/C++, this variable is a pointer (because pointers are variables that store memory addresses). Here, this variable will be a pointer to a Node.
• Printing addresses. To print the addresses of the node, you can use printf with the formatting flag “%p”, e.g., printf(“Address: %p”, current ) prints the address stored at the pointer current.
• Joining the lists is just the initial setting of the problem and you can do it manually with some setting of your program. Think of this structure as two nameless one-way roads that intersect. Once the intersect, each path can be a whole path, the concept of short or long lists does not exist because you can distinguish one list from the other, i.e., the configuration

  node —> node —> node —> node —> node —> NULL
  /
  /
  node —> node —/

  is equivalent to (and indistinguishable from) the configuration:

  node —> node —> node —

  /
  node —> node —> node —> node —> NULL

  The lists have “no color” so we can’t tell them apart once they are connected. The length values have no meaning.
  The only thing we know is that the total of nodes is m+n, where m, n are the lengths of the lists.

  The number of nodes in each of the lists before they intersect is unknown and may be different in each list. List1 may have n nodes before it reaches the intersection point, and List2 might have m nodes before it reaches the intersection point where m and n may be m = n, m < n or m > n.

Some sample code

The following examples might help you with this assignment:

1. A simple example of a singly linked list. (simple_singly_linked_list.pdf) This example creates two lists and prints the addresses of the nodes.

2. Another version of the simple singly linked list (Simple_singly_linked_list2.pdf).This version passes the pointer to the head by reference to the functions. This is done by using a double pointer. See code for details.

3. The simple singly linked list using classes(Simple_singly_linked_list3.pdf). This version uses a basic Object-Oriented design. Here, I tried to keep things simple by adapting the previous examples almost directly. The main difference is that the functions that act on the list are now part of the class List. In this way, we keep Data + Functions together in a single “container”, which is implemented in the class. I also replaced printf with cout and malloc/free with new/delete to try to use as much C++ as possible.

4. Starter code. I wrote an example program that creates the two-headed list and calls the function to find the intersection node. The code can be found here: (sample-code.pdf) You can use this code and extend it to implement the functions you need for the assignment. The current version of the function just traverses the list starting from each head. To complete the function, you will need to create two stacks (create them using the list as the basis implementation). Then, follow the steps given in the assignment description. This program is not a great code. To be honest, it is a quite ugly because it mixes the class framework with a function that is not in a class. This is not good practice. But, I wanted to get an example that you can use so I adapted the code from the linked-list example. Compile and run this code, and see the results. I commented the code to help you follow the steps.