We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
- Merge two sorted linked lists
- Discussions
Merge two sorted linked lists
Merge two sorted linked lists
+ 1 comment java recursive solution
static SinglyLinkedListNode mergeLists(SinglyLinkedListNode head1, SinglyLinkedListNode head2) { if(head1 == null){ return head2; } if(head2 == null){ return head1; } if(head1.data < head2.data){ SinglyLinkedListNode nextSortedHead = mergeLists(head1.next, head2); head1.next = nextSortedHead; return head1; }else{ SinglyLinkedListNode nextSortedHead = mergeLists(head1, head2.next); head2.next = nextSortedHead; return head2; } }
+ 2 comments js recursive
function mergeLists(head1, head2) { if (!head1) return head2 if (!head2) return head1 if(head1.data < head2.data){ return {"data": head1.data, "next": mergeLists(head1.next, head2)} }else{ return {"data": head2.data, "next": mergeLists(head1, head2.next)} } }
+ 4 comments python solution:
def mergeLists(head1, head2): if not head1 and not head2: return head1 if not head1: return head2 if not head2: return head1 res = SinglyLinkedListNode(None) c = res c1 = head1 c2 = head2 while c1 and c2: print(res) if c1.data <= c2.data: c.next = c1 c1 = c1.next else: c.next = c2 c2 = c2.next c = c.next if c1: c.next = c1 if c2: c.next = c2 return res.next
+ 0 comments simple c# code with comments to help you parse it;
{ //this seems simple, if the lists are sorted, all you need to do is compare each head and insert //the smallest one into the new list; //the trickiest part of this would be proper node pointer management //we need a link to the head of the sorted list and a iterator pointer //to make sure we don't lose our place. SinglyLinkedListNode sorted = new SinglyLinkedListNode(0); SinglyLinkedListNode ind= new SinglyLinkedListNode(0); //point the sorted list to the first element in the list if(head1.data <= head2.data){ sorted = head1; //point start of list at it ind = head1; //point iterator at it head1 = head1.next; //move head1 pointer over 1 } else{ sorted = head2; // point start of list at it ind = head2; // point iterator at it head2 = head2.next;//move head2 pointer over 1 } while( head1 != null || head2!= null) { if(head1 == null && head2 != null){ //continue down head2 ind.next = head2; ind = ind.next; head2 = head2.next; //make sure to move head2 over } else if(head1 !=null && head2 == null){ //head2 is null and we can continue down head1 ind.next = head1; ind = ind.next; head1= head1.next; // make sure to move head1 over } else if(head1.data <= head2.data && ind.next == head1){ //head1 is the next lowest number and i next is pointing to it //so we just need to move head1 over 1 as well as i over on same list; head1 = head1.next; ind = ind.next; } else if(head1.data <= head2.data && ind.next==head2){ //head1 is the next lowest number and i next is not pointing to it //we need to make i next point to head1 then move head1 and iterator over ind.next = head1; head1 =head1.next; ind = ind.next; } else if(head1.data > head2.data && ind.next== head1){ //head2 is the next lowest data and i next is not pointing to it //make i next point to head2 and move head2 and iterator over ind.next = head2; head2 = head2.next; ind = ind.next; } else{ //head2 is next lowest dat and i next is pointing to it //move head2 and iterator over head2 =head2.next; ind = ind.next; } } return sorted; }
+ 0 comments Since the maximum number of elements is only 1000, you can use a simple trick here, 1) first get all the elements into a LIST and then sort it 2) afterwards you can create a new LInkedList from the sorted list
def mergeLists(head1, head2): my_list = [] node = head1 while node is not None: my_list.append(node.data) node = node.next node2 = head2 while node2 is not None: my_list.append(node2.data) node2 = node2.next my_list.sort() ll3 = SinglyLinkedList() for num in my_list: ll3.insert_node(num) return ll3.head
Load more conversations
Sort 62 Discussions, By:
Please Login in order to post a comment