Why would you sort sorted lists.
There is no need of a stack. (Pen and paper. Watch yourself not use a stack. If you don’t do it with pen and paper then don’t do it in code.)

What you would do with pen and paper is look at the front of each list. Pick the smaller value, cross out the node. Append the value to the result.
You can write down what basic operations are involved in this, mark out the part that repeats, put that in a loop.

but they arent sorted. one of the tasks is to sort them

They’re sorted, that’s the point. Read the description or even just the title of the problem.

The overall operation you’re asked to implement is: given two lists, produce a single sorted list containing all elements from those two lists.

Oof, you’re right. I meant combing the two lists wont automatically produce a sorted list.

Getting a sorted list from two sorted lists is much easier than sorting all those elements. You’re not supposed to sort. They are sorted. Combine them in a way that preserves that. Pen and paper.
Actually, this is a way to sort them, because if you start with size-1 lists and repeatedly merge those lists then you will end up with an overall sorted list.

So just like how you shouldn’t be using a python list to implement a list, you also shouldn’t be using python’s sort to implement sort.

Not mine but it works. Where is the information stored throuugh each iteration? Does he rewrite l2 and l1?

``````        if not l1:
return l2
if not l2:
return l1
if l1.val < l2.val:
l1.next = self.mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = self.mergeTwoLists(l1, l2.next)
return l2
``````

It picks a node and merges the rest

…but you should be able to execute that yourself with, you guessed it, pen and paper.

Draw two lists, do what it says.

The nodes are already there, simply point them at the result of the rest.
Note, each line separates a node from the rest (so the process is very much representable on paper)

… It’s a linked list, so once you have the first node, all you need to do is to point at the next thing. Repeat until through.

How would you call this function with completely new linked lists?
what would you write as parameters? (how do you write a linked list as a parameter?)

…?

``````a = define a list here
b = define a list here
function(a, b)
``````

A linked list is a value, you’d pass it around the same way as an integer or string.

but how do you literally write it

``````1 -> 3 ->4
``````

I cant put this as a parameter

But you can create a bunch of nodes linked that way.

and set it equal to an object?

set what equal to what?

If you have a value then you have a value.
If you have a list then you have a list

Make a list. Assign a variable to the list.
Make another list. Assign another variable to that list.
Call your function with those values as arguments.

Or for that matter define the lists in the function call, here using empty lists:

``````merge(None, None)
``````
``````        if not l1:
return l2
if not l2:
return l1
if l1.val < l2.val:
l1.next = self.mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = self.mergeTwoLists(l1, l2.next)
return l2
``````

So is `return` only used once in this code or is it used multiple times? And I’m not talking about the number of times its written, but the number of times it is used in the example we’ve been using

You could write code to keep count

I thought return ends a function

It must be different when you call it several times in the same function

if you can’t do it after returning then do it before