מריה בוטוסוב

נותנים 2 רשימות מקושרות שכל אחד מהן ממוינת. צריך למזג אותם ללא שימוש במבנים אחרים.

public static LinkedList merge(LinkedList headOne, LinkedList headTwo) {
    LinkedList p1 = headOne;
    LinkedList p1Prev = null;
    LinkedList p2 = headTwo;
    while(p1 != null && p2 != null) {
        if(p1.value < p2.value) {
            p1Prev = p1;
            p1 = p1.next;
        } else {
            if(p1Prev != null)
                p1Prev.next = p2;
            p1Prev = p2;
            p2 = p2.next;
            p1Prev.next = p1;
        }			
    }
    /*lets say:
    first list is 0
    second list is 1->2->3
    so we need fix now last pointer of first list to point to second pointer
    */
    if(p1 == null) 
        p1Prev.next = p2;
    /* let's say in previous example, we need return first..*/	
    return headOne.value < headTwo.value ? headOne : headTwo;
}