Requirement: start from define the node, construct a linked list, the insertion
ID: 3531263 • Letter: R
Question
Requirement: start from define the node, construct a linked list, the insertion method ensure the linked list is sorted.
/**
* Given two sorted linked list, merge the two linked list into one sorted linked list. Duplication allowed.
*
@author
*
*/
public
class LinkedList {
/**
* add val into correct position. The order in this linkedList is form lowest to highest, such as 1 2 3 4 5
*
@param val the value will be add into linked list
*/
public void add(int val){
}
/**
* show all element in the list
*/
public String toString(){
return null;//change null to your variable
}
/**
* merge two linked list l1 and l2 together in the correct order, from lowest to highest
*
@param l1
*
@param l2
*
@return result
*/
public static LinkedList merge(LinkedList l1,LinkedList l2){
return null;//change null to your variable
}
/**
* test function
*
@param args
*/
public static void main(String[] args){
LinkedList l1 =
new LinkedList();
LinkedList l2 =
new LinkedList();
l1.add(8);
l1.add(9);
l1.add(2);
System.out.println(l1);
//{2, 8, 9}
l2.add(4);
l2.add(9);
l2.add(5);
System.out.println(l2);
//{4, 5, 9}
System.out.println(merge(l1,l2));
//{2, 4, 5, 8, 9, 9}
}
}
//hint: you need develop your own Node class
Explanation / Answer
Please rate with 5 stars :)
You have two lists that are already sorted, you have to merge them and return a new list without any new extra nodes. The returned list should be sorted as well.
The method signature is,
Node* MergeLists(Node* list1, Node* list2);
struct Node{
int data;
Node *next;
}
The following is the solution I came up with,
Node* MergeLists(Node* list1, Node* list2){
Node* mergedList;
if(list1 == null && list2 ==null){//if both are null, return null
return null;
}
if(list1 == null){//if list1 is null, simply return list2
return list2;
}
if(list2 == null){//if list2 is null, simply return list1
return list1;
}
if(list1.data < list2.data){//initialize mergedList pointer to list1 if list1's data is lesser
mergedList = list1;
}else{//initialize mergedList pointer to list2 if list2's data is lesser or equal
mergedList = list2;
}
while(list1!=null && list2!=null){
if(list1.data < list2.data){
mergedList->next = list1;
list1 = list1->next;
}else{
mergedList->next = list2;
list2 = list2->next;
}
}
if(list1 == null){//remaining nodes of list2 appended to mergedList when list1 has reached its end.
mergedList->next = list2;
}else{//remaining nodes of list1 appended to mergedList when list2 has reached its end
mergedList->next = list1;
}
return mergedList;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.