Question Problem 1 (Graded) In chapter 1 you learned how to merge two sorted lists and get a third list which is also sorted. Write a method named mergeUnsorted Lists in an application, which given two unsorted lists list1 and list2, merge their nodes together to make one new list list3, by taking nodes alternately between the two lists. For example, if list! contains [1, 5, 3] and list2 contains [7, 13, 11, 8, 10 then they will be merged into list3 which would look like [1, 7, 5, 13, 3, 11, 8, 10]. Note that if either list (list) or list2) runs out of nodes, then all the nodes in the other list should be added to list3. Write a main method to test this method. The header of the method is given below. public static LinkedList mergeUnsortedLists (LinkedList listi, Linkedlist list2) { Problem 2 (Ungraded) Given the below Linked List named list1, show the content of the linked list result after the code is executed. list1 head 25 80 90 8 45 → 67 56 LinkedList result = new LinkedList(); Node curr = listi.getHead(); int i = 0; while (curr != null) { if (i82 == 0) result.addHead (curr.getData()); else result.addTail (curr.getData()); curr = curr.getNext(); i++; 1 The content of the linked list result is: Problem 3 (Ungraded) Given the below Linked List named list1, show the output of the below code fragment. list1 head 17 6 3085 25 → 51 34 Output Node curr - listi.getHead(); while (curr.getNext() != null) { System.out.println(curr.getData().getValue()); curr - curr.getNext().getNext();
4IU4GU The Asker · Computer Science
Transcribed Image Text: Problem 1 (Graded) In chapter 1 you learned how to merge two sorted lists and get a third list which is also sorted. Write a method named mergeUnsorted Lists in an application, which given two unsorted lists list1 and list2, merge their nodes together to make one new list list3, by taking nodes alternately between the two lists. For example, if list! contains [1, 5, 3] and list2 contains [7, 13, 11, 8, 10 then they will be merged into list3 which would look like [1, 7, 5, 13, 3, 11, 8, 10]. Note that if either list (list) or list2) runs out of nodes, then all the nodes in the other list should be added to list3. Write a main method to test this method. The header of the method is given below. public static LinkedList mergeUnsortedLists (LinkedList listi, Linkedlist list2) { Problem 2 (Ungraded) Given the below Linked List named list1, show the content of the linked list result after the code is executed. list1 head 25 80 90 8 45 → 67 56 LinkedList result = new LinkedList(); Node curr = listi.getHead(); int i = 0; while (curr != null) { if (i82 == 0) result.addHead (curr.getData()); else result.addTail (curr.getData()); curr = curr.getNext(); i++; 1 The content of the linked list result is: Problem 3 (Ungraded) Given the below Linked List named list1, show the output of the below code fragment. list1 head 17 6 3085 25 → 51 34 Output Node curr - listi.getHead(); while (curr.getNext() != null) { System.out.println(curr.getData().getValue()); curr - curr.getNext().getNext();
More Transcribed Image Text: Problem 1 (Graded) In chapter 1 you learned how to merge two sorted lists and get a third list which is also sorted. Write a method named mergeUnsorted Lists in an application, which given two unsorted lists list1 and list2, merge their nodes together to make one new list list3, by taking nodes alternately between the two lists. For example, if list! contains [1, 5, 3] and list2 contains [7, 13, 11, 8, 10 then they will be merged into list3 which would look like [1, 7, 5, 13, 3, 11, 8, 10]. Note that if either list (list) or list2) runs out of nodes, then all the nodes in the other list should be added to list3. Write a main method to test this method. The header of the method is given below. public static LinkedList mergeUnsortedLists (LinkedList listi, Linkedlist list2) { Problem 2 (Ungraded) Given the below Linked List named list1, show the content of the linked list result after the code is executed. list1 head 25 80 90 8 45 → 67 56 LinkedList result = new LinkedList(); Node curr = listi.getHead(); int i = 0; while (curr != null) { if (i82 == 0) result.addHead (curr.getData()); else result.addTail (curr.getData()); curr = curr.getNext(); i++; 1 The content of the linked list result is: Problem 3 (Ungraded) Given the below Linked List named list1, show the output of the below code fragment. list1 head 17 6 3085 25 → 51 34 Output Node curr - listi.getHead(); while (curr.getNext() != null) { System.out.println(curr.getData().getValue()); curr - curr.getNext().getNext();
Community Answer
MPGT7A
public class Solution { public LinkedList mergeUnsortedLists(LinkedList l1, LinkedList l2){ LinkedList p1 = sortList(l1); LinkedList p2 = sortList(l2); return mergeTwoLists(p1,p2); } private LinkedList sortList(LinkedList head) { if(head==null || head.next==null) return head; //base case LinkedList slow = head, fast=head, preMid = head; //keep track of previous node of slow while(fast!=null&&fast.next!=null){ fast = fast.next.next; preMid = slow; slow = slow.next; } preMid.next = null; //split list into two parts LinkedList left = sortList(head); LinkedList right = sortList(slow); //now slow is the middle node return mergeTwoLists(left,right); } //method to merge two sorted lists private LinkedList mergeTwoLists(LinkedList l1, Li ... See the full answer