1

I have an integer linked list of which both first half and second half are sorted independently.Now i need to merge two parts to create one single sorted linked list.

Sample input:

Input List 1: 1->2->3->4->5->1->2
Output : 1->1->2->2->3->4->5

Input List 2: 1->5->7->9->11->2->4->6
Output 2: 1->2->4->5->6->7->9->11

Expected output:

1,2,3.....

10
  • 3
    The expected final output is 1,2,3? Why is that?
    – jogojapan
    Nov 7, 2012 at 7:46
  • Naively this is the same as sorting an initially unsorted list, for which there are a number of common solutions.
    – Chris
    Nov 7, 2012 at 7:47
  • 1
    Does your linked-list implementation provide an iterator interface and begin() and end() style functions? In that case you can use the std::merge algorithm: en.cppreference.com/w/cpp/algorithm/merge
    – jogojapan
    Nov 7, 2012 at 7:50
  • 1
    @billz The expected output is still not really clear. I assumed it's 1,1,1,2,2,2,3,4,4,5,5,6,7,9,11. But perhaps it is 1,2,4,5, in which case we need an intersection algorithm.
    – jogojapan
    Nov 7, 2012 at 7:53
  • @jogojapan This is two separate test cases. Each one has two sorted groups in a single linked list. So the outputs are 1,1,2,2,3,4,5 for test case 1 and 1,2,4,5,6,7,9,11 for test case 2. So it's merge sort, not set intersection.
    – abarnert
    Nov 7, 2012 at 8:00

5 Answers 5

2

This is merge sort.

I will maintain two pointers:

ptr1 points to the first half's first element

and ptr2 points to the second half's first element.

you will need an extra array to store the final list, of course you can choose not to use this extra array, but that discussion is far away from the topic.

1, Compare *ptr1 and *ptr2, if *ptr1's value is smaller than *ptr2, then copy that value(i.e. *ptr1) to the final array, and let ptr1 move forward.

if ptr2's value is the smaller one, just copy *ptr2 and let ptr2 move forward

2, Stop when the pointer points after the last element, say if you have 5 elements in the first half a[0] a[1] a[2] a[3] a[4], then you should stop when the pointer points to a[5]

3, If the first half is empty, then copy the rest of the second half, vice versa.

3
  • 2
    The particular step is called merge which joins two already sorted lists/arrays in O(n). He would probably not need a new list. Instead of copying elements you can always swap pointers
    – fkl
    Nov 7, 2012 at 7:58
  • Oh yeap, he said he has one big list which first half and second half is sorted, I'm saying the steps for two separated lists.
    – shengy
    Nov 7, 2012 at 8:10
  • That's the point. If both of them are actual link lists (and not arrays) it doesn't matter.
    – fkl
    Nov 7, 2012 at 8:14
0

This is called merge sort.

Look here and here for implemetation details.

0

Look for natural merge sort for optimal solution: http://en.wikipedia.org/wiki/Merge_sort#Natural_merge_sort

0

I have done that countless time when using functional languages, so I guess I can give you a short explanation.

It's easier to grasp the idea if you think of it as a recursive process, but I'll give you the imperative one. You start off with both your partial lists, and an empty sorted list.

Then you start your loop, your partial lists can be seen as:

  • both empty, in which case your processing is done,
  • one of them empty, you append the other to your sorted list,
  • a couple of head elements and the tails of the lists, where you will compare both heads, add the smallest to your sorted list, leave the other one in its original place, then loop with your remaining lists.

Once out of the loop you just return the sorted list.

There's one caveat though: if you are using simple linked lists, you'll get better running time by adding the elements in front of the sorted list, and reverse it at the end before returning it.

2
  • damn, typing that on a smartphone sucks. :)
    – didierc
    Nov 7, 2012 at 8:08
  • 1
    That's because you can't just recursively type the first character and then the rest; you need an algorithm with explicit backtracking. :)
    – abarnert
    Nov 7, 2012 at 8:10
0
int[] merge(int[] left, int[] right) {
        int[] ret = new int[left.length + right.length];

        int i = 0;
        int j = 0;
        for (; i < left.length & j < right.length;) {
            if (left[i] < right[j]) {
                ret[i + j] = left[i++];
            } else if (left[i] > right[j]) {
                ret[i + j] = right[j++];
            } else {
                ret[i + j] = left[i];
                ret[i + j + 1] = left[i];
                i++;
                j++;
            }
        }

        if (i < left.length) {

            copyIntArray(left, i, left.length, ret, ret.length - i);
        } else if (j < right.length) {

            copyIntArray(right, j, right.length, ret, ret.length - j);
        }

        return ret;
    }

    void copyIntArray(int[] src, int startIndex, int endIndex, int[] des, int desStartIndex) {
        for (int i = startIndex; i < endIndex; i++) {
            des[desStartIndex++] = src[i];
        }
    }

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.