Question: I am attempting to splice (concatenate) two full std::lists in constant time. From reading the documentation and other questions
([How to do range splice in constant time with std::forward\_list?](https://stackoverflow.com/questions/14170746/how-to-do-range-splice-in-constant-time-with-stdforward-list)), I have two clarification questions:

1. Is it possible to splice two std::lists in constant time and retain the full list of each?
2. My understanding is that this functionality could be achieved by creating my own list data structure - and using a function similar to the following (pseudocode):

```
List joinLists(List list1, List list2) {

  list1->tail = list2->head;

  list1->tail = list2->tail;

  return list1;

}

```

Is this true? If not, I would appreciate if someone can help me understand what's going on here. I feel like I'm missing something..

The code that I am working with is here:

```
 auto simple_sorter = [this, numCores](std::vector<std::vector<std::list<unsigned int>>>& buckets_small_, std::vector<std::list<unsigned int>>& buckets_large_, std::vector<bool>& finished_, unsigned int range_low, unsigned int range_high, int thread_number)
{
    //.. irrelevant

    //Combine small buckets into single large bucket per thread
    for(unsigned int i = 0; i < numCores; ++i) {
        std::list<unsigned int> list1 = buckets_large_[thread_number];
        list1.splice(list1.end(), buckets_small_[i][thread_number]);

    //...
};

```

(Note: Boost/other libraries are not an option)

Answer: 
1. Yes, and `std::list::splice` works this way (has O(1) complexity)[(1)](http://en.cppreference.com/w/cpp/container/list/splice):

> 
> No elements are copied or moved, only the internal pointers of the list nodes are re-pointed. 
> 
> 
> 

2. Assuming an abstract single-linked list, you would do

```
list1->back->next = list2->front;
list1->size += list2->size;

```

For a double-linked list, you would also do 

```
list2->front->prev = list1->back;

```

If you want to insert elements of `list2` after `n`th element of `list1`, you will need to find that element, and do the same thing

```
element->next = list2->front;        
//for a double-linked list:
list2->front->prev = element;

```

In either case, no data is copied, you just swap pointers here and there.
(Below is pseudo code)

Splicing is interweaving:

`new_list = list1[0], list2[0], list1[1], list2[1], ...`

concatenating is joining two lists together:

`new_list = list1, list2`

(Below is (slightly less pseudo) code that is untested)

to splice:

```
List splice(List list1, List list2){
  List<stuff> things ;
  List<stuff> * small_list = list1.size() > list2.size() ? &list2 : &list1 ;
  List<stuff> * big_list = list1.size() > list2.size() ? &list1 : &list2 ;
  for(int i = 0 ; i < small_list->size() ; i++ ){
    things << list1[i] << list2[i] ;
  }
  for(int i = small_list->size() ; i < big_list->size()){
    things << (*big_list)[i] ;
  }
  return things ;
}

```

Pretty sure you have to define what your list is containing in the return value and arguments (or use templates for polymorphism, which are beyond me right now)

Disclaimer: I have been spoiled by ruby and forgotten if this is valid c++...