Skip navigation
2012

[Introduction]

 

One day when I read someone interview experiences. I find he had been asked this kind of question, and he provided the solution accordingly. But I thought his solution wasn't so correct at some level. So here I want to present more accurate one for you.

 

[Consideration]

 

Several things we should consider before begin your coding.

1. Will the two sorted linked list have the same sorted order?

    For example:  LinkedList A:{1,2,3}       LinkedList B:{7,6,5}


2. Will the final merged linked list has the sorted order request? 

    For example:    LinkedList A: {1,2,3}        LinkedList B: {4,5,6}        but expected result is {6,5,4,3,2,1}

 

3. Whether or not allow change the amount of data ?

     For example:  Whether or not allow remove the redundant data.

 

4. Whether or not exist the memory limitation ?

 

[Code snippet]

 

Here I have several assumptions:

1. Memory could holding the whole data.

2. Sorted order could be random

3. Assume the output sorted order is big-ending - from smaller to bigger

4. Should not remove any data from the two lists.

5. Using java

 

If you want to check the accuracy you could goto here for checking.

 

goto http://www.leetcode.com/onlinejudge  and below the issue list you find "Merge two sorted lists", then click ">> solve the problem". And copy my codes into coding panel, please remember language be selected as Java. You can click "Judge Small" or "Judge Large". Right now the result is 100% pass.

 

Reading codes from here isn't comfortable, so you download the attachment files into your ide or copy the coding panel. And the "png" file is the guideline how to use "leetcode" website.

 

 

/**

* Definition for singly-linked list.

* public class ListNode {

*     int val;

*     ListNode next;

*     ListNode(int x) {

*         val = x;

*         next = null;

*     }

* }

*/

public class Solution {

   

    enum SORTED_ORDER {

        LITTLE_ENDING, BIG_ENDING

    }

   

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        // Start typing your Java solution below

        // DO NOT write main() function

        /**

         * The solution need consider several factors:

         * 1. the sorting order for two list

         * 2. the output list sorting order

         * 3. memory limition. Please remember assumption could hold within memory.

         * 4. Whether or not allow change the merged result, like remove redudant data.

         *

         */        

         //Based on that here assume the output sorted order will be BIG_ENDING

        ListNode result = null;

        if (l1 == null && l2 == null) return null;

        if (l1 == null && l2 != null) return sort(l2, SORTED_ORDER.BIG_ENDING);

        if (l1 != null && l2 == null) return sort(l1, SORTED_ORDER.BIG_ENDING);

        ListNode tmpNode1 = sort(l1, SORTED_ORDER.BIG_ENDING);

        ListNode tmpNode2 = sort(l2, SORTED_ORDER.BIG_ENDING);

        //Begin some sort of merge sort

        ListNode bNode = null;

        boolean oneListFinished = false;

        do {

            ListNode tNode = null;

            if (tmpNode1 != null && tmpNode2 != null) {

                if (tmpNode1.val <= tmpNode2.val) {

                    //tNode = new ListNode(tmpNode1.val);

                    tNode = tmpNode1;

                    tmpNode1 = tmpNode1.next;

                } else {

                    //tNode = new ListNode(tmpNode2.val);

                    tNode = tmpNode2;

                    tmpNode2 = tmpNode2.next;

                }

            } else if (tmpNode1 != null) {

                //tNode =  new ListNode(tmpNode1.val);

                tNode = tmpNode1;

                tmpNode1 = tmpNode1.next;

                oneListFinished = true;

                //break;

            } else if (tmpNode2 != null) {

                //tNode = new ListNode(tmpNode2.val);

                tNode = tmpNode2;

                tmpNode2 = tmpNode2.next;

                oneListFinished = true;

                //break;

            }

            if (bNode != null) {

                bNode.next = tNode;

                bNode = tNode;

                if (oneListFinished) break;

            } else {

                bNode = tNode;

                result = tNode;

            }

           

        } while (tmpNode1 != null || tmpNode2 != null);

        return result;

    }

   

    public ListNode sort(ListNode l3, SORTED_ORDER order) {

        SORTED_ORDER l3Order = SORTED_ORDER.BIG_ENDING;

        ListNode tmpNode = l3;

        if (tmpNode.next != null && tmpNode.val > tmpNode.next.val) {

            l3Order = SORTED_ORDER.LITTLE_ENDING;

        }

        if (l3Order != SORTED_ORDER.BIG_ENDING) {

           ListNode movedNode = tmpNode.next;

           while (movedNode != null) {

               ListNode immNode = movedNode.next;

               movedNode.next = tmpNode;

               tmpNode = movedNode;

               movedNode = immNode;

           }

        }

        return tmpNode;

    }

}