Java Reference
In-Depth Information
merging two ordered lists without creating new cells. We will then make use of
this merging function to provide an e
cient sorting procedure.
7.6.1 Merging ordered lists
Let us consider two ordered linked lists
u
and
v
of arbitrary lengths with
corresponding cells storing integers in increasing order. That is, the sequence
of integers stored in cells from the head to the tail is increasing in both lists.
We would like to create a
new
linked list merging the elementary cells of
u
and
v
in increasing order
without
creating any new cell. To make it plain, we need
to recycle the elementary cells already available in
u
and
v
when building the
merged list. To provide an illustrating example, the list merging operation will
give the following result:
u
3
−−>
6
−−>
8
−−>
null
v
2
−−>
4
−−>
5
−−>
7
−−>
9
−−>
null
Merge(u,v)
2
−−>
3
−−>
4
−−>
5
−−>
6
−−>
7
−−>
8
−−>
9
−−>
null
We consider the following class
List
that defines the basic blocks of integer
linked lists.
class
List
int
container ;
List next ;
// Constructor List(head, tail)
List(
int
element , List tail )
{
this
.container=element;
this
.next=tail;
}
// Insert element at the head of the list
List insert (
int
el)
{
return new
List(el ,
this
);
}
void
Display ()
{
List u=
this
;
while
(u!=
null
)
System . out . print (u . container+
"-->"
);
u=u . n e x t ;
}
System . out . println (
"null"
);
}
}
So that the above two example integer linked lists are created in the
main
procedure as follows:
Search WWH ::
Custom Search