Comparing two linked lists and returing a list with maximum values

Question

I am planning to write a Java Function that takes two linked lists. Both have the same size. I want to return a new list that contains the maximum of the data found in the corresponding nodes of the two lists passed to my function.

However I am stuck in filling the new list. I came up with this:

function max2List (LinkedList list1 , LinkedList list2) {
    LinkedList <int> list3 = new LinkedList<int> ();
    for (ListNode p = list1.first ; p!=null; p=p.next) {
        for (ListNode p = list2.first ; p!=null; p=p.next) {
            if (list1.p.data > list2.p.data ) {
                //return list3 here with big value
            else if (list1.p.data < list2.p.data ) {
               //return list3 here with big value

I don't know how to continue. I want list3 to contain the maximum values from the two lists.

When you say you want the "maximum of the data..." do you mean the single largest element in each list or do you want a larger subset of the largest data elements in each list? Top half from each list? Top x% of the merged lists? — mba12, Dec 01 '16 at 18:35
I mean the single largest element in each list to be put in a new list — GenreicITStudent, Dec 01 '16 at 18:40

Michael · Accepted Answer · 2016-12-02T13:43:49.757

1

Firstly, what you have written is not valid Java. Generics cannot use primitive types, such as the use of <int> in your example. It needs to be a class e.g. <Integer>. function is also not a keyword.

For brevity, the following code assumes both lists are of equal size:

public static List<Integer> max2List (List<Integer> list1, List<Integer> list2)
{
    List<Integer> maxValues = new LinkedList<>();

    for (int i = 0; i < list1.size(); ++i)
    {
        // If item in list1 is larger, add it
        if (list1.get(i).compareTo(list2.get(i)) > 0)
        {
            maxValues.add(list1.get(i));
        }
        else // else add the item from list2
        {
            maxValues.add(list2.get(i));
        }
    }

    return maxValues;
}

edited Dec 02 '16 at 13:43

answered Dec 01 '16 at 18:31

Michael

41,989
11
82
128

Sorry my mistake in the first line but I was thinking of creating a loop that goes in the first list find the biggest value put it in a new list then a second loop that goes in the second list finds the biggest value and put it in the new list basically list3 should contain the maximum values from both lists – GenreicITStudent Dec 01 '16 at 18:35
Are you saying list3 should always contain exactly 2 items - the biggest item from list one and the biggest item from list two? – Michael Dec 01 '16 at 18:39
It should contain the biggest values like list1 = 3->7->5->null list2 = 2->1->5->null then list3 = 3->7->5->null – GenreicITStudent Dec 01 '16 at 18:44
You're giving me conflicting requests now. Your comment on the question states you want the **single largest element in each list to be put in a new list**. I have updated my answer to reflect that. That is **not** what you have just described. If it were, your list3 should be `7 -> 5 -> null`. – Michael Dec 01 '16 at 18:47
Sorry then I meant what I just described It should contain the biggest values like list1 = 3->7->5->null list2 = 2->1->5->null then list3 = 3->7->5->null shouldn't I create loops for that ? – GenreicITStudent Dec 01 '16 at 18:53
I'd like you to very carefully explain the logical process that results in the answer you're looking for. Try to avoid the word 'biggest'. I'm trying my best to understand what you want but you're not making it easy. For example, do you add all the values in each list `3+7+5 = 15` and `2+1+5 = 8` and return whichever list has the greatest total? – Michael Dec 01 '16 at 18:58
first is we have 2 lists they list1, list2 then create a new list called list3, list3 values should be the largest values from the two lists, if list1 values were 3->7->5->null and list2 values were 2->1->5->null then list3 should be created and its values should be the from the 2 previous lists 3->7->5->null respectively so it contains the largest values from the two previous lists with respect to the positions, for that I think I should create a loop for each list and search for the largest value put it in list3 ? – GenreicITStudent Dec 01 '16 at 19:10
Right, I think I'm with you. So to get the 1st element of list three, we should look at the 1st element of list one and the 1st element of list two and choose the largest. To get the 2nd element of list three, we should look at the 2nd element of list one and the 2nd element of list two and choose the largest. And so on. Correct? – Michael Dec 02 '16 at 10:22
Exactly and I need loops and if statements for that right ? – GenreicITStudent Dec 02 '16 at 12:11
Many thanks it does help but a small question why ++i not i++ ? – GenreicITStudent Dec 02 '16 at 15:29
In this case it makes no difference. `i++` will work just as well. [Read more here if you're interested](http://stackoverflow.com/a/17367081/1898563). – Michael Dec 02 '16 at 15:39

score 0 · Answer 2 · answered Aug 22 '21 at 00:04

def compare_lists(node_1, node_2): 

  while True:
      if not node_1 and not node_2:
          return 1
    
      if (not node_1) ^ (not node_2):
          return 0
    
      if node_1.data != node_2.data:
          return 0
    
      node_1 = node_1.next
      node_2 = node_2.next

Comparing two linked lists and returing a list with maximum values

2 Answers2