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
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.
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.
© 2024 OneMinuteCode. All rights reserved.