Skip to content

Instantly share code, notes, and snippets.

@danarbaugh
Created March 21, 2011 07:42
Show Gist options
  • Save danarbaugh/879151 to your computer and use it in GitHub Desktop.
Save danarbaugh/879151 to your computer and use it in GitHub Desktop.
java method for merging two ordered linked lists
public OrderedLinkedList mergeLists(OrderedLinkedList<T> list1, OrderedLinkedList<T> list2){
OrderedLinkedList<T> mergedList = new OrderedLinkedList<T>();
LinkedListNode<T> list1Current = list1.first;
LinkedListNode<T> list2Current = list2.first;
LinkedListNode<T> newNode = new LinkedListNode<T>();
while(list1Current != null && list2Current != null){
Comparable<T> temp1 = (Comparable<T>) list1Current.info; // temp var for casted info comparable
if (temp1.compareTo(list2Current.info) >= 0){
if (mergedList.first == null) // if mergedList is empty, start it
{
mergedList.first = new LinkedListNode<T>();
mergedList.first.info = list2Current.info;
mergedList.first.link = new LinkedListNode<T>();
newNode = mergedList.first.link;
}else{
newNode.info = list2Current.info;
newNode.link = new LinkedListNode<T>();
newNode = newNode.link;
}
list2Current = list2Current.link;
count++;
// list1Current is higher, so insert list2Current
}else{
if (mergedList.first == null) // if mergedList is empty, start it
{
mergedList.first = new LinkedListNode<T>();
mergedList.first.info = list1Current.info;
mergedList.first.link = new LinkedListNode<T>();
newNode = mergedList.first.link;
}else{
newNode.info = list1Current.info;
newNode.link = new LinkedListNode<T>();
newNode = newNode.link;
}
list1Current = list1Current.link;
count++;
// list2Current is higher, so insert list1Current
}//end comparable else
}//end while
if(list1Current == null){ // if list1 is done, append list2
while(list2Current != null){
newNode.info = list2Current.info;
if(list2Current.info != list2.last.info){newNode.link = new LinkedListNode<T>();
newNode = newNode.link;}
list2Current = list2Current.link;
count++;
}
}
if(list2Current == null){ // if list2 is done, append list 1
while(list1Current != null){
newNode.info = list1Current.info;
if(list1Current.info != list1.last.info){newNode.link = new LinkedListNode<T>();
newNode = newNode.link;}
list1Current = list1Current.link;
count++;
}
}
return mergedList;
} // end mergeLists
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment