I want to sort a consolidated list that shares two or more nodes.

Is there a way to sort the two ascending concatenated lists that share the last few nodes into one concatenated list in ascending order?

For example,

-900->120->200->230
                   \
                    452->700
                   /
           -10 - > 200

If it's a consolidated list,

-900->-10->120->200->200->230->452->700

I would like to do so.
Only the first pointer of the node is given here.

For now, I came up with a way to get the length of each list, take the absolute value of the difference |m-n|, proceed with the pointer of the longer list, compare the nodes one by one, sort the elements, and stick them directly into the linked list after the intersection.I would appreciate your help.

Additional
Could you also give me some advice on how to determine the common areas?

Note 2
Thank you for your reply.If I use merge, it will be O(nlogn), but is there any way I can do it with O(n)?
Note 3
Merge method self-resolved

algorithm data-structure

2022-09-30 18:15

2 Answers

Wouldn't it be okay to leave this merge algorithm as it is?
https://ja.wikipedia.org/wiki/ Merge

If we match the common parts, we only need to output from one side.

2022-09-30 18:15

Merge should be done normally.

Determining if you have reached the beginning of a shared node at the end depends on how you implement a consolidated list.

If it is managed by a pointer and the physical equality between nodes can be determined, you can use it.Please note that the processing changes depending on whether you simply connect shared parts or double the number of nodes.

If physical equality is not available,

...--- 10--- 20--- 30
                   |
... --- 15 --- 20 -|

and

...--- 10--- 20--- 30
            |
... --- 15 -|

Because you can't tell the difference between , you're likely to simply create a new node without doing anything special.However, if you want to leave it as one instead of increasing the end of the shared part to two, you should not put a flag in the data structure indicating that it is a shared part.

2022-09-30 18:15

If you have any answers or tips

Popular Tags

python x 4647

android x 1593

java x 1494

javascript x 1427

c x 927

c++ x 878

ruby-on-rails x 696

php x 692

python3 x 685

html x 656