Sortowanie listy dwukierunkowej przez scalanie - rozdzielanie listy

Question

Zaproponuj algorytm rozdzielania listy dwukierunkowej

ze szczególnym uwzględnieniem przypadków brzegowych

 

Myślę z pozostałymi funkcjami potrzebnymi do realizacji sortowania przez scalanie bym sobie

poradził choć chciałbym poznać wasz pomysł na konkatenacje bo

występuje ona podczas scalania

 

Scalanie dwóch posortowanych list

Scalanie(L,A,B)

      L=NIL

     dopóki lista A jest niepusta oraz lista B jest niepusta wykonuj

            Jeżeli klucz pobrany z głowy listy A jest mniejszy bądź równy kluczowi pobranemu z głowy listy B to

                              Usuń węzeł z głowy listy A i zapamiętaj go w lokalnej zmiennej

              w przeciwnym przypadku

                              Usuń węzeł z głowy listy B i zapamiętaj go w lokalnej zmiennej

              Wstaw zapamiętany węzeł na koniec listy L

     /* Teraz co najmniej jedna lista powinna być pusta ale nie wiemy która więc

         łączymy obie listy A oraz B z listą L  przy czym łączenie to redukuje się do tzw konkatenacji */

     Połącz listę L z listą A

     Połącz  listę L z listą B

 

Sortowanie(L)

      Jeżeli głowa listy L nie pokazuje na NIL oraz następnik głowy listy L nie pokazuje na NIL to

                 Rozdziel listę L na połowę

                 Posortuj rekurencyjnie obydwie połowy

                 Scal posortowane połowy

Answer 1

taki prototypik dla jedno kierunkowej // ale bez kompilacji

list * new_list (list * N_element){
        list * temp = new list;
        temp=N_element->next;
        N_element->next=nullptr;
        return temp;
}

 

Comments

Ja bym tak spróbował: Rozdzielamy listy na dwie połówki. Wywołujemy rekurencyjnei dla każdej połówki. Jak połówka jest krótka, to sortujemy inaczej, np. gdy ma dwa elementy, to robimy swap. Pewności nie mam, ale powinno zadziałać. Można też zwalić do wektora, posortować wektor i odbudować listę.

Można upewnić się, czy std::sort (nie)działa dla listy dowiązywanej.

---

może bzdura, ale 24h powisi taki prototypik

Scalanie dwóch posortowanych list

http://wklejto.pl/790509

---

@fisker,

 

struct Node 
{
      struct Node *prev;
      int key;
      struct Node *next;
};

struct List
{
        struct Node *head;
        struct Node *tail;
};



void Split(struct Node *x,struct List L,struct List *L1,struct List *L2)
{
      // x to węzeł za którym należy rozdzielić listę 
      // L lista którą należy rozdzielić 
      // L1, L2 listy powstałe po rozdzieleniu listy L

     /* Jak należałoby taką listę rozdzielić 
       z uwzględnieniem przypadków brzegowych 
    Mile widziana gotowa funkcja lub przynajmniej 
    pseudokod w postaci listy kroków */
}

Wątpię czy twój prototypik będzie działał , nie uwzględniasz przypadków brzegowych

---

Porzuć listę dwukierunkową z metodami samosprawdzającymi add  .... Głową ogonem to się pobawię. Cała dwukierunkowa to trochę klepania. Jedno  kierunkową mam, ale to taka trochę niestandardowa to i tak nie pomoże.

Sam się uczę na przykładach tutaj podanych wiec to co pisze może być mało profesjonalne.

Ale jak na tygodniu znajdę czas to na pewno zrobię sobie to zadanie ale nie wiem czy to nie będzie za późno.

---

Zdaje się że przetłumaczyłem listę dwukierunkową z przykładu znalezionego

w książce Roberta Lafore Struktury danych i algorytmy w Javie

Od siebie dopisałem szablony a gettery i settery wzorowane są na tych

automatycznie  generowanych przez IDE

Przetłumaczonej klasy użyłem do wyznaczenia otoczki wypukłej za pomocą

algorytmu Jarvisa którego opis znalazłem gdzieś na rosyjskiej stronie internetowej

---

Gratuluję!

---

@fisker,
 skoro się uczysz to pobaw się tą listą

Dopisz np wstawianie węzła przed podanym elementem,

usuwanie powtórzeń z posortowanej listy

Do wstawiania węzła przed podanym elementem

można wykorzystać już istniejące funkcje jak

insertFirst,

insertLast,

insertAfter

tylko trzeba odpowiednio rozbić tę funkcję na przypadki

 

Lafore ma też wstawianie do jednokierunkowej listy uporządkowanej

Można tę funkcję zmodyfikować aby działała też dla listy dwukierunkowej

jednak kod nie będzie optymalny

 

template<class T>
void DoublyLinkedList<T>::insert(T key,int (*Compare)(T,T))
{
          Link<T>  *newLink = new Link<T> (dd);
          Link<T> *previous = NULL;
          Link<T>  *current  =  getFirst();
          while(current != NULL && Compare(key , current->getData()) > 0)
          {
                 previous = current;
                 current = current->getNext();
          }
         if(previous == NULL)
               setFirst(newLink);
         else
              previous->setNext(newLink);
         newLink->setNext(current);
         // Jak dokończyłbyś wstawianie do uporządkowanej listy dwukierunkowej ?
}

Tutaj funkcja wstawiająca wymaga dokończenia jeśli chcemy aby działała także dla listy dwukierunkowej

Tutaj funkcja po dokończeniu nie będzie optymalna ponieważ lista jest iterowana dwoma wskaźnikami

i nie wykorzystujemy tego że każdy węzeł listy dwukierunkowej zawiera zarówno wskaźnik na następnika jak i wskaźnik na poprzednika

---

@fisker, co do twojej propozycji scalania 

to może jednak zanim przystąpimy do scalania zajmiemy się

rozdzielaniem i konkatenacją ?

---

Wczoraj późno było(kiedyś trzeba spać) dzisiaj zapowiada się że też z czasem krucho.

Proszę rozdzielenie dla poprzedniej

void Split(struct Node *x,struct List L,struct List *L1/*wyzerowane*/)
{
     Node* temp=L.head; // ustawiamy wskaźnik równy glowie// temp by głowy nie przesuwać;
    Node* temp2=nullptr;
    
     
    //element na samym poczatku
    if(x->key==L.head->key){
    
        L1->head=L.head;//"przkopiowanie" bez ruszania z miejsca
        L1->tail=L.tail;//"przkopiowanie" bez ruszania z miejsca
        
        //zerwanie wiązaniań listy L
        Node * tempH=new Node();// wyzerowane elementy ale z adresem
        Node * tempL=new Node();// wyzerowane elementy ale z adresem
        L.head=tempH;//by nie pozmieniać L1
        L.tail=tempL;//by nie pozmieniać L1
        L.head=nullptr;//teraz wskazuje na nic
        L.tail=nullptr;//teraz wskazuje na nic
        delete tempH;
        delete tempL;
    }
    // powtarzaj dopóki wartość x bedze różna niż temp
    // i temp jest różne od nullptr założenie tail->next=nullptr
     while (x->key!=temp->key and temp){temp=temp->next;}
     
     if(temp/*temp!=nullptr*/){
         Node* temp2=temp->next;//ustawienie wskaznika na następny element po temp
         temp2->prev=nullptr; // zerwanie wiązania wstecznego;
         temp->next=nullptr; //oderwanie wszystkiego co za temp-key=x->key;
     } else {std::cout<<"Nie znaleziono elemetu\n L1 jest puste\n"<<endl;
         return;
     }
    
        if (temp2)// jesli istnieje /*temp!=nullptr*/
        { L1->push(temp2);// skoro L1 jest pusta to powinno dodać się do głowy push musisz za implemetowac
           // ale to zalezy od implemetaci pusz();
            // da się zrobić i na nie pustej od biedy

        } else {std::cout<<"Lista L1 jest pusta"<<endl;}
     
    
    // x to węzeł za którym należy rozdzielić listę 
      // L lista którą należy rozdzielić 
      // L1, L2 listy powstałe po rozdzieleniu listy L / L2 to niebardzo kumam o co chodzi przy rozdielaniu
 
     /* Jak należałoby taką listę rozdzielić 
       z uwzględnieniem przypadków brzegowych 
    Mile widziana gotowa funkcja lub przynajmniej 
    pseudokod w postaci listy kroków */
}

konkatenacja - dodajesz do next tail pierwszej  head drugiej przez tempa i ok zerujesz listy

Answer 2

Fisker masz przykładową listę dwukierunkową

#include <iostream>
#include <fstream>
#include <string>
#include <sstream>

using namespace std;

struct Point
{
      int x,y;
      friend std::ostream &operator << (std::ostream &output,const Point &p);
      friend std::istream &operator >> (std::istream &input,Point &p);
};

bool operator == (Point a,Point b)
{
     return (a.x == b.x && a.y == b.y); 
}

std::ostream &operator << (std::ostream &output,const Point &p)
{
        output<<"( "<<p.x<<" , "<<p.y<<" ) ";
        return output;
}



std::istream &operator >> (std::istream &input,Point &p)
{
        input>>p.x>>p.y;; 
        return input;
}


template<class T>
class Link
{
      private:
              T data;
              Link<T> *next;
              Link<T> *previous;
      public:
             Link(T data);
             void displayLink();
             T getData();
             void setData(T data);
             Link<T> *getNext();
             void setNext(Link<T> *next);
             Link<T> *getPrevious();
             void setPrevious(Link<T> *previous);
             template<class U> friend std::ostream& operator<< (std::ostream& print, Link<U>& obj);

};

template<class T>
Link<T>::Link(T data)
{
     setData(data);
     setNext(NULL);
     setPrevious(NULL);
                
}

template<class T>
void Link<T>::displayLink()
{
     std::cout<<getData()<<" ";
}

template<class T>
T Link<T>::getData()
{
     return data;               
}

template<class T>
void Link<T>::setData(T data)
{
     this->data = data;               
}

template<class T>
Link<T> *Link<T>::getNext()
{
      return next;  
}

template<class T>
void Link<T>::setNext(Link<T> *next)
{
      this->next = next; 
}

template<class T>
Link<T> *Link<T>::getPrevious()
{
      return previous;  
}

template<class T>
void Link<T>::setPrevious(Link<T> *previous)
{
      this->previous = previous; 
}


template <class U>  
std::ostream& operator<<(std::ostream& print, Link<U> & L)
{
        print << L.getData();
        return print;
}

template<class T>
class DoublyLinkedList
{
      private:
              Link<T> *first;
              Link<T> *last;
      public:
             DoublyLinkedList();
             ~DoublyLinkedList();
             Link<T> *getFirst();
             void setFirst(Link<T> *first);
             Link<T> *getLast();
             void setLast(Link<T> *first);
             bool isEmpty();
             Link<T> *find(T key);
             void insertFirst(T dd);
             void insertLast(T dd);
             void deleteFirst();
             void deleteLast();
             bool insertAfter(T key,T dd);
             void deleteKey(T key);
             void displayForward();
             void displayBackward();
};

template<class T>
DoublyLinkedList<T>::DoublyLinkedList()
{
    setFirst(NULL);
    setLast(NULL);                                   
}

template<class T>
DoublyLinkedList<T>::~DoublyLinkedList()
{
    while(!isEmpty())
    {
        deleteFirst();             
    }                                   
}

template<class T>
Link<T> *DoublyLinkedList<T>::getFirst()
{
       return first; 
}

template<class T>
void DoublyLinkedList<T>::setFirst(Link<T> *first)
{
     this->first = first;
}

template<class T>
Link<T> *DoublyLinkedList<T>::getLast()
{
       return last; 
}

template<class T>
void DoublyLinkedList<T>::setLast(Link<T> *last)
{
     this->last = last;
}

template<class T>
bool DoublyLinkedList<T>::isEmpty()
{
     return getFirst()==NULL;
}

template<class T>
 Link<T> *DoublyLinkedList<T>::find(T key)
 {
         Link<T> *current = getFirst();
         while(current != NULL && !(current->getData == key))
               current = current->getNext();
         return current;        
 }
 
 template<class T>
 void DoublyLinkedList<T>::insertFirst(T dd)
 {
      Link<T> *newLink = new Link<T>(dd);
      if(isEmpty())
           setLast(newLink);
      else
          getFirst()->setPrevious(newLink);
      newLink->setNext(getFirst());
      setFirst(newLink);        
 }
 
 template<class T>
 void DoublyLinkedList<T>::insertLast(T dd)
 {
      Link<T> *newLink = new Link<T>(dd);
      if(isEmpty())
      {
          setFirst(newLink);         
      }
      else
      {
          getLast()->setNext(newLink);
          newLink->setPrevious(getLast());
      }
      setLast(newLink);
 }
 
 template<class T>
 void DoublyLinkedList<T>::deleteFirst()
 {
      if(isEmpty())
           return;
      Link<T> *temp = getFirst();
      if(getFirst()->getNext() == NULL)
            setLast(NULL);
      else
         getFirst()->getNext()->setPrevious(NULL);
      setFirst(getFirst()->getNext());
      delete temp;                            
 }
 
 template<class T> 
 void DoublyLinkedList<T>::deleteLast()
 {
      if(isEmpty())
         return;
      Link<T> *temp = getLast();
      if(getFirst()->getNext() == NULL)
             setFirst(NULL);
      else
          getLast()->getPrevious()->setNext(NULL);
      setLast(getLast()->getPrevious());
      delete temp;                  
 }
 
 template<class T>
 bool DoublyLinkedList<T>::insertAfter(T key,T dd)
 {
      Link<T> *current = find(key);
      if(current == NULL)
             return false;
      Link<T> *newLink = new Link<T>(dd); 
      if(current->getNext() == NULL)
      {
           newLink->setNext(NULL);
           setLast(newLink);                 
      }
      else
      {
          newLink->setNext(current->getNext());
          current->getNext()->setPrevious(newLink);
      }
      newLink->setPrevious(current);
      current->setNext(newLink);
      return true;    
 }
 
 template<class T>
 void DoublyLinkedList<T>::deleteKey(T key)
 {
      Link<T> *current = find(key);
      if(current==NULL)
           return;
      if(current->getPrevious() == NULL)
             setFirst(current->getNext());
      else
             current->getPrevious()->setNext(current->getNext());
      if(current->getNext() == NULL)
             setLast(current->getPrevious());
      else
             current->getNext()->setPrevious(current->getPrevious());
      delete current;
 }
 
 template<class T>
 void DoublyLinkedList<T>::displayForward()
 {
      std::cout<<"List (first-->last): ";
      Link<T> *current = getFirst();
      while(current != NULL)
      {
         current->displayLink();
         current = current->getNext();   
      }
      std::cout<<"\n";
 }
 
 template<class T>
 void DoublyLinkedList<T>::displayBackward()
 {
      std::cout<<"List (last-->first): ";
      Link<T> *current = getLast();
      while(current != NULL)
      {
         current->displayLink();
         current = current->getPrevious();   
      }
      std::cout<<"\n";
 }



int vect(Point a1,Point a2,Point b1,Point b2)
{
    return (a2.x - a1.x)*(b2.y - b1.y) - (b2.x - b1.x)*(a2.y - a1.y);
}

int dist2(Point a1,Point a2)
{
    return (a2.x - a1.x)*(a2.x - a1.x) + (a2.y - a1.y)*(a2.y - a1.y);
}

void Solve(DoublyLinkedList<Point> &A,DoublyLinkedList<Point> &B)
{
     Link<Point> *p,*q,*m,*min;
     if(!A.isEmpty())
     {
         m = A.getFirst();
         p = m->getNext();
         while(p != NULL)
         {
              if(p->getData().y < m->getData().y)   
                  m = p;
              else if(p->getData().y == m->getData().y && p->getData().x > m->getData().x)              
                   m = p;
              p = p->getNext();
         }
         
         if(m->getPrevious() == NULL)
              A.setFirst(m->getNext());
         else
             m->getPrevious()->setNext(m->getNext());
         if(m->getNext() == NULL)
            A.setLast(m->getPrevious());
         else
             m->getNext()->setPrevious(m->getPrevious());
         
         if(A.isEmpty())
            A.setLast(m);
         else
             A.getFirst()->setPrevious(m);
         m->setNext(A.getFirst());
         m->setPrevious(NULL);
         A.setFirst(m);
         
         B.insertLast(A.getFirst()->getData());
         
         if(A.getFirst()->getNext() != NULL)
             min = A.getFirst()->getNext();
         else
             min = A.getFirst(); 
         
         do
         {
             q = A.getFirst()->getNext();
             while(q != NULL)
             {
                 if((vect(B.getLast()->getData(),min->getData(),B.getLast()->getData(),q->getData()) < 0)||
                 (vect(B.getLast()->getData(),min->getData(),B.getLast()->getData(),q->getData()) == 0)&&
                 (dist2(B.getLast()->getData(),min->getData()) < dist2(B.getLast()->getData(),q->getData())))
                    min = q;
                 q = q->getNext();    
             }
             B.insertLast(min->getData());
             min = A.getFirst();
         }
         while(!(B.getLast()->getData() == B.getFirst()->getData()));
         B.deleteLast();
     }
}

int main(int argc, char *argv[])
{
    DoublyLinkedList<Point> A;
    DoublyLinkedList<Point> B;
    stringstream ss;
    Point p;
    string line;
    int counter;
    while(getline(cin,line))
    {
       ss.clear();
       ss.str(line);
       counter = 1;
       while(ss)
       {
           try
           {
               switch(counter)
               {
                   case 1:
                   {
                       ss>>p.x;
                       break;
                   }
                   case 0:
                   {
                       ss>>p.y;
                       A.insertLast(p);
                       break;
                   }
               }
           }
           catch(...)
           {
               
           }
           counter = (counter + 1)%2;
       }
        Solve(A,B);
        cout<<"List A \n";
        A.displayForward();
        A.displayBackward();
        cout<<"List B \n";
        B.displayForward();
        B.displayBackward();
        while(!A.isEmpty())
            A.deleteFirst();
        while(!B.isEmpty())
            B.deleteFirst();
    }    
    return EXIT_SUCCESS;
}

Dopisz funkcje realizujące sortowanie przez scalanie

Funkcję porównującą przekaż jako argument funkcji sortującej

Jeżeli będziesz chciał użyć tej klasy tak ja do wyznaczania wypukłej otoczki to

tam funkcja porównująca ma trzy argumenty

 

Comments

dużo czytania, nic strasznego nie widzę

Edit:: poświęciłem czas którego nie powinienem i poległem na sortowaniu :(

---

Jeżeli zrezygnowałeś z L2 to przydałoby się przekazać listę L przez wskaźnik

Jakie będą przypadki brzegowe dla rozdzielania listy

 

Znalazłem funkcję rozdzielającą listę jednokierunkową na połówki

i próbowałem zmodyfikować ją tak aby działała także dla listy dwukierunkowej

" Edit:: poświęciłem czas którego nie powinienem i poległem na sortowaniu : "

 

Wcześniej pisałeś że jeszcze się uczysz czyżbyś kłamał ?

---

może trochę późno

"uczę się c++" (tj staram się nie zapomnieć tego co umiem)

i własne wymysły funkcji podziel u mnie błędu nie wywaliło, globalnie bo już nie chciałem kombinować,

///----------------------------------------
using dllp=DoublyLinkedList<Point>;

//void divdllp(Point P, dllp *A)
void divdllp(Point P, dllp *A,dllp * B)
{


    Link<Point> *temp;

    temp=A->find(P);
    if(temp==nullptr){
        std::cout<<"\n don't find \n";
    }
    else if(temp==A->getFirst()) {
        std::cout<<"\ntemp==A.getFirst()\n";

        B->setFirst(A->getFirst());   // (A->getFirst());
        B->setLast(A->getLast());
        A->setLast(nullptr);
        A->setFirst(nullptr);
        A->setdestructor(0);

    }
    else if(temp==A->getLast()){
                    std::cout<<"\ntemp==A.getLast()\n";

                }
    else {
                    std::cout<<"\ninner element\n";
                    Link<Point> *temp2=temp->getNext();

                    temp2->setPrevious(nullptr);
                    B->setFirst(temp2);   // (A->getFirst());
                    B->setLast(A->getLast());

                    temp->setNext(nullptr);
                    A->setLast(temp);
                }

}

a to reszta twojego kodu. http://wklejto.pl/791751

Postaram się dołączyć resztę funkcji. Jak znajdę chwilę wolnego;

//---------------------------------------------------------------------------------------------------------------

Edit:: sortowanie ogarnięte trochę "trochę po Grubiańsku"

efekt uboczny O(n)vector = O(n) list chyba;

- getdata i delete first musiałem pozmieniać bo mi kompilator psuło;

void sort_dllp (dllp &A){
    std::vector<Point> v;
    Link<Point>* B=A.getFirst();

    while(B) {

        v.push_back(B->getData(B));

        A.deleteFirst();
        B=A.getFirst();
        std::cout<<B->getData(B)<<"|";
    }
    std::cout<<B->getData(B)<<"\n";
    delete B;
    A.setFirst(nullptr);
    A.setLast(nullptr);

    std::sort(begin(v),end(v));

    for(auto &x:v) std::cout<<x<<"|";
    for(auto &x:v) A.insertLast(x);
}

 

---

No obiecałem to wszystko razem ale nie przez konkatenację.

Pewnie toi znacznie można uprość, ale ten czas:)

24h  http://wklejto.pl/792909

---

A właśnie co by się stało gdyby do scalania tych resztek chciał użyć konkatenacji  ?

Kiedyś na podstawie opisu algorytmu oraz pseudokodu

przedstawionego przez użytkownika .kassad napisałem sortowanie listy przez łączenie naturalne

Teraz po każdym rozdzielaniu następuje scalanie

Przy czym jedno rozdzielanie musi być wykonane co najmniej raz aby sprawdzić

czy lista jest posortowana

Algorytm można jednak nieco przyspieszyć

Masz na to jakiś pomysł

---

A właśnie co by się stało gdyby do scalania tych resztek chciał użyć konkatenacji  ?

nic więcej pisania bym miał i musiałbym prev ustawiać.

 

przedstawionego przez użytkownika .kassad napisałem sortowanie listy przez łączenie naturalne

nie wiem o jaki algorytm chodzi wiec nie będę się wypowiadał, ale

Algorytm można jednak nieco przyspieszyć

Na początku miałem taki pomysł by dane podmieniać przez wartość i listy nie ruszać, ale coś się wywalało i sobie odpuściłem. bo to parę rzeczy bym musiał sobie przypomnieć.

A tu łączenie dwóch list

#define o(a) #a
void concat1(dllp* A, dllp* B){


    if(!B->getFirst()) {std::cout<<"\nlista "<<o(A)<<" jest pusta\n";
        return;}
    if(!A->getFirst()) {std::cout<<"\nlista "<<o(B)<<" jest pusta\n";
        return;}

    B->getFirst()->setPrevious(A->getLast());
    A->getLast()->setNext(B->getFirst());
    A->setLast(B->getLast());

    B->setFirst(nullptr);
    B->setLast(nullptr);

}

edit:: jakby była funkcja insertLast(LINK<T>*) to by znacznie można by to to uprościć

---

nie wiem o jaki algorytm chodzi wiec nie będę się wypowiadał,

Chodzi mi o algorytm w wątku

https://forum.pasja-informatyki.pl/425346/sortowanie-przez-laczenie-naturalne-mozliwosc-usprawnienia-algorytmu

 

Jakiś czas temu użytkownik .kassad opisał mi ten algorytm

i podał mi pseudokod który niestety musiałem poprawić

 

Poprawiłem pseudokod podany przez użytkownika .kassad

i przystosowałem podany algorytm do sortowania list

Chciałbym ten algorytm trochę usprawnić , przyspieszyć ale .kassad już nie wchodzi na forum a nikt inny się nie zainteresował i nie mam z kim pisać o tym jak przyspieszyć ten kod

 

Na początku miałem taki pomysł by dane podmieniać przez wartość i listy nie ruszać, ale coś się wywalało i sobie odpuściłem

Z tego co jeden koleś z innego forum twierdził to jest to wina destruktora

Destruktor zwalniając pamięć na lokalną kopię zwalnia też pamięć na węzły oryginalnej listy Co o tym myślisz ? Miałoby to sens ?

Jeśli chodzi o konkatenację to przypadek gdy jedna z list jest pusta też przydałoby się obsłużyć .Jeżeli jedna z list jest pusta wynikiem jest ta druga lista a w przypadku gdy obie listy są puste wynikiem jest pusta lista

W przypadku gdy mamy wskaźnik zarówno na głowę jak i ogon można całkiem zgrabny kod dla konkatenacji napisać

 

@fisker

Widziałeś następującą stronę ?

http://wazniak.mimuw.edu.pl/index.php?title=Strona_g%C5%82%C3%B3wna

oraz algorytmy i struktury danych Banachwskiego , Diksa i Ryttera

 

---

tak jak pisałem wcześniej, z czasem różnie. To co wiem to piszę, nie szukam.

Wina destruktora

Ja nie chciałem destruktora wywoływać nie wien czy przez R wartość, wywołuje  się destruktor, Ciałem skopiować podmienić i to wszystko jak w zwykłym swap() ale nie cały węzeł, tylko wartość typu jaki przechowuje.

Destruktor zwalniając pamięć na lokalną kopię zwalnia też pamięć na węzły oryginalnej listy Co o tym myślisz ? Miałoby to sens

na lokalna kopię tak, ale dlatego trzeba włożyć do oryginału. A oryginalnej listy nie zwalnia bo przekazujesz tylko wskaźniki na listę, a nie samą.

co do reszty to poczytam.

edit:: znowu się spieszyłem i wyszło masło maślane, new na stercie to nie jest lokalna kopia i można dołączać. a na stosie to usunie. Ale poczekam jak ogarnę temat to napiszę, bo zaraz, coraz to większe bzdurki będę pisał.

---

@Mariusz M,

Algorytm można jednak nieco przyspieszyć

pisanie na pewno tak używając STL; http://www.cplusplus.com/reference/list/list/

24h -->http://wklejto.pl/793554;

A co do szybkości w C kiedyś było szybciej chyba a teraz nie wiem?