问题描述

链表的二路归并 求大神发完整的代码！！不会写啊！

题目：设有n个待排序元素存放在一个不带表头结点的单链表中, 每个链表结点只存放一个元素, 头指针为r。试设计一个算法, 对其进行二路归并排序, 要求不移动结点中的元素, 只改各链结点中的指针, 排序后r仍指示结果链表的第一个结点。

解决方案

http://wenku.baidu.com/link?url=X2Dpb0WQDM9YCJJj5a9n06t_jE9e_B3ElDT_-6h-JHoFiNrdrAshoye8cfwaNbtveEgyxTFCJag2AsJyE-hRno3W79Y2u6Qxeq0AeUNvbNW

解决方案二：

代码稍微有点长：

 // teste0100.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"

template<typename T>
class List
{
private:
    struct Node
    {
        T data;
        Node* next;
        Node(const T& t=T()):data(t)
        {next=NULL;}
    };
    Node* head;
    Node* getPointer(int pos)
    {
        Node* p=head;
        for(int i=0;i<pos;i++)
            p=p->next;
        return p;
    }
public:
    List():head(NULL){};
    void clear()
    {
        while(head!=NULL)
        {
            Node* p = head->next;
            delete head;
            head = p;
        }
    }
    ~List()
    {
        clear();
    }
    void insert_front(const T& t)
    {
        Node* p = new Node(t);
        p->next = head;
        head = p;
    }
    void travel()
    {
        Node* p = head;
        while(p!=NULL)
        {
            cout<<p->data<<' ';
            p = p->next;
        }
        cout << endl;
    }

    void insert_back(const T& t)
    {
        Node* p = new Node(t);
        if(head == 0)
            head = p;
        else
        {
            getPointer(size()-1) -> next = p;
        }
    }
    int size()
    {
        int cnt = 0;
        Node* p = head;
        while(p != NULL)
        {
            cnt++;
            p = p->next;
        }
        return cnt;
    }
    T getHead()
    {
        if(head == NULL)
            throw "No Head";
        return head->data;
    }
    T getTail()
    {
        if(head == NULL)
            throw "No Tail";
        Node* p = head;
        while(p->next != NULL)
        {
            p = p->next;
        }
        return p->data;
    }
    bool empty()
    {
        return head==NULL;
    }
    int find(const T& t)
    {
        int pos = 0;
        Node* p = head;
        while(p!=NULL)
        {
            if(p->data == t)
                return pos;
            pos++;
            p = p->next;
        }
        return -1;
    }
    bool updata(const T& o, const T& n)
    {
        int pos = find(o);
        if(pos == -1)
            return false;
        Node* p = getPointer(pos);
        p->data = n;
        return true;
    }

    bool erase(const T& t)
    {
        int pos = find(t);
        if(pos == -1)
            return false;
        if(pos == 0)
        {
            Node* p = head->next;
            delete head;
            head = p;
        }
        else
        {
            Node* pre = getPointer(pos-1);
            Node* cur = pre->next;
            pre->next = cur->next;
            delete cur;
        }
        return true;
    }
};

解决方案三：

最近刚写过一篇博客，不过是基于C++的，供你参考：http://blog.csdn.net/cxsmarkchan/article/details/50850499
代码在这里：https://github.com/cxsmarkchan/mySTL/blob/master/lib/list_impl.h
里面的stable_sort函数就是二路归并。
都是个人的理解，希望对你有帮助。