单链表(带头结点、不带头结点、带头结点循环)

程序小白，希望和大家多交流，共同学习

//带头结点的单链表
#include<iostream>

using namespace std;

struct Node
{
    int data;
    Node * next;
};

typedef struct Node Node,*LinkList; 

//初始化
void initLink(LinkList &l);
//头插法创建链表
void createLinkFromHead(LinkList l);
//尾插法创建链表
void createLinkFromTail(LinkList l);
//按照给定位置删除结点
void deleteNode(LinkList l, int index);
//输出
void outputLink(LinkList l);
//求链表长度
int getLength(LinkList l);
//按值查找
Node * getUseData(LinkList l, int num);
//按位置查找
Node * getUseIndex(LinkList l, int index);
//插入
void insert(LinkList l, int index, int data);
//合并两个链表
void merge(LinkList lA, LinkList lB, LinkList &lC);
//逆置一个链表
void invert(LinkList l);

int main()
{
    int index, num;
    LinkList l;
    initLink(l);
    LinkList nL;
    initLink(nL);
    LinkList finalL;
    initLink(finalL);
    cout << "创建链表" << endl;
    //createLinkFromHead(l);
    createLinkFromTail(l);
    outputLink(l);

    cout << getLength(l) << "个结点" << endl;
    cout << "按值查找，输入数值：";
    cin >> num;
    cout << getUseData(l, num) << endl;

    cout << "按下标查找，输入数值：";
    cin >> index;
    Node *result = getUseIndex(l, index);
    cout << (result == NULL ? 0 : result -> data) << endl;

    cout << "插入数据，输入插入位置，和新的数值: " << endl;
    cin >> index >> num;
    insert(l, index, num);
    outputLink(l);

    cout << "翻转链表: " << endl;
    invert(l);
    outputLink(l);
    invert(l);

    cout << "创建新的链表\n";
    createLinkFromTail(nL);
    outputLink(nL);
    cout << "合并两个链表 \n";
    merge(l, nL, finalL);
    outputLink(finalL);
    return 0;
}
//初始化
void initLink(LinkList &l)
{
    //初始化带头结点的链表，L是一个链表的节点，但是这个结点的数据域为空
    l = new Node;
    l -> next = NULL;
}

//头插法创建链表
//头插法创建链表，就是使用每次输入的值创建一个结点，
//然后将这个结点加到已知链表的头结点的后面
void createLinkFromHead(LinkList l)
{
    int num;
    Node *s;
    bool input = true;
    while (input)
    {
        cin >> num;
        if (num == -1)
        {
            break;
        }

        s = new Node;
        s -> data = num;

        s -> next = l -> next;
        l -> next = s;  
    }
}
//尾插法创建链表
//尾插法和头插法类似，也是按照每次输入的值创建一个结点，
//然后将这个结点连接到已知链表的表尾
//但是链表作为一个链式结构是不容易找到表尾的，
//所以要有一个变量指向这个表尾，那么每次对输入的值的添加就简单了
void createLinkFromTail(LinkList l)
{
    Node *t = l, *n;
    bool input = true;
    int num;
    while (input)
    {
        cin >> num;
        if (num != -1)
        {
            n = new Node;
            n -> data = num;
            t -> next = n;
            t = n;
        }
        else
        {
            input = false;
            t -> next = NULL;
        }
    }
}
//按照给定位置删除结点，找到的是前驱
//删除紧跟着前驱的下一个位置的节点，所以前驱不能到达链表的结尾
//找到要删除的位置的前驱，然后跳过要删除的对象，直接指向下一个位置
void deleteNode(LinkList l, int index)
{
    Node *pre = l, *n;
    if (index < 0)
    {
        cout << "删除结点不存在" << endl;
        return ;
    }
    int i = 0;
    while (pre -> next != NULL && i < index - 1)//找的是前驱，所以是index - 1
    {                                           //删除有可能删除最后一个，所以前驱不能够到最后。
                                                //到最后之后就找不到后面要删除的结点
        pre = pre -> next;
        i++;
    }
    if (pre -> next == NULL)
    {
        cout << "输入位置错误" << endl;
        return ;
    }

    n = pre -> next;
    pre -> next = n -> next;
    delete n;
}
//输出
void outputLink(LinkList l)
{
    Node *s = l -> next;
    while (s != NULL)
    {
        cout << s -> data << " ";
        s = s -> next;
    }
    cout << endl;
}
//求链表长度
int getLength(LinkList l)
{
    int len = 0;
    Node *s = l -> next;
    while (s != NULL)
    {
        s = s -> next;
        len++;
    }
    return len;
}
//按值查找
//按照给定的值寻找结点，和按位置找结点相似，需要在遍历过程中把每个结点的
//数据域和给定的值进行比较
Node * getUseData(LinkList l, int num)
{
    Node *p = l -> next;
    //按值查找，对于带头结点的链表，第一个结点的数据域为空，
    //所以要找一个指针，指向头结点的下一个位置
    while (p != NULL)//扫描到链表的最后一个之前，如果匹配传递过来的值，就返回当前结点，
    {                   //不匹配就，就判断下一个结点
        if (p -> data != num)
        {
            p = p -> next;
        }
        else
            break;
    }
    return p;
}
//按位置查找
//按照给定位置找到结点，那就是遍历链表，找到给定的位置
Node * getUseIndex(LinkList l, int index)
{
    Node *s = l;
    if (index <= 0)
    {
        return NULL;
    }

    int i = 0;
    while ((s -> next != NULL) && (i < index))//在保证i在等于index之前，链表的元素存在
    {       
        s = s -> next;
        i++;
        //cout << i << " ";
    }
    if (i == index)
    {
        return s;
    }
    else
        return NULL;
}
//插入
void insert(LinkList l, int index, int data)
{
    if (index < 0)
    {
        cout << "插入点不能小于零" << endl;
        return;
    }

    Node *pre = l, *n;
    //pre作为前驱，也就是找到要插入位置的前一个结点的位置
    //找到位置之后，使用n将data作为它的数据域，创建一个结点，然后将这个结点插入前驱后面
    int i = 0;
    while (pre != NULL && i < index - 1)//找的是前驱，所以是index - 1
    {                                   //插入有可能是在最后插入，所以只要判断pre不为空就好
                                        //pre为最后一个结点时，就在最后插入
        pre = pre -> next;
        i++;
    }
    if (pre == NULL)
    {
        cout << "插入位置超出范围" << endl;
        return ;
    }

    n = new Node;
    n -> data = data;
    n -> next = pre -> next;
    pre -> next = n;
}
//合并两个链表
//将新的链表指向其中一个链表，然后将原来的两个链表的每个结点的值进行比较，
//数值较小的就连接到新的链表后面，并把较小的节点位置向后移动一个结点，
//再进行比较，以此重复。最后将新的链表，指向剩余的链表
void merge(LinkList lA, LinkList lB, LinkList &lC)
{
    Node *p, *q, *n;//将 *p 设置为指向lA的指针变量，*q 设置为指向lB的指针变量
                    // *n 指针始终指向链表lC的最后，然后按照尾插法，将所有的数值串联起来
    p = lA -> next;
    q = lB -> next;

    lC = lA;//使用链表lA作为基本链表
    lC -> next = NULL;//将lC初始化为空链表
    n = lC;//n 始终指向lC的表尾

    while (p && q)
    {
        if (p -> data <= q -> data)
        {
            n -> next = p;
            n = p;
            p = p -> next;
        }
        else
        {
            n -> next = q;
            n = q;
            q = q -> next;
        }
    }
    //当 p 或 q其中有一个已经到达表尾，那么剩下的可以直接连接
    if (p)
    {
        n -> next = p;
    }
    if (q)
    {
        n -> next = q;
    }
    //最后将多余的表头lB删除
    delete lB;
    //return lC;
}

//这是一个连续的不断的将每一个结点变成头结点下一个结点的过程
void invert(LinkList l)
{
    Node *p, *q;
    p = l -> next;//将p初始化为头结点
    l -> next = NULL;//为链表设置尾结点
    while (p)
    {
        q = p -> next;//q用来储存p的下一个结点，以便将p不断向后移动
        p -> next = l -> next;//将p指向头结点的下一个结点
        l -> next = p;//将头结点指向p。原来的头结点的指向被取消

        p = q;
    }
}

//不带头结点的单链表
#include <iostream>
using namespace std;

struct Node
{
    int data;
    Node * next;
};

typedef struct Node Node,*LinkList; 

//初始化
void initLink(LinkList &l);
//头插法创建链表，链表在初始化之后就是一个空值，
//在插入结点时候，改变头指针的值，所以传值为引用
void createLinkFromHead(LinkList &l);
//尾插法创建链表
void createLinkFromTail(LinkList &l);
//按照给定位置删除结点
void deleteNode(LinkList &l, int index);
//输出
void outputLink(LinkList l);
//求链表长度
int getLength(LinkList l);
//按值查找
Node * getUseData(LinkList l, int num);
//按位置查找
Node * getUseIndex(LinkList l, int index);
//插入
void insert(LinkList &l, int index, int data);
//合并两个非递减链表
void merge(LinkList lA, LinkList lB, LinkList &lC);
//逆置一个链表
void invert(LinkList &l);

int main()
{
    LinkList l;
//  initLink(l);
//  createLinkFromHead(l);
//  outputLink(l);
    initLink(l);
    createLinkFromTail(l);
    outputLink(l);
//  cout << "输入删除结点的坐标:";
//  int index;
//  cin >> index;
//  deleteNode(l, index);
//  outputLink(l);
    cout << "此时链表的长度为: ";
    cout << getLength(l) << endl;
//  cout << "按值查找，请输出要查找的值:";
//  int num;
//  cin >> num;
//  Node * node = getUseData(l, num);
//  cout << ((node == NULL) ? 0 : (node -> data)) << endl;
//  cout << "按下标查找，请输出要查找的值:";
//  int index;
//  cin >> index;
//  Node * node = getUseData(l, index);
//  cout << ((node == NULL) ? 0 : (node -> data)) << endl;
//  cout << "插入，输入插入位置和数值:";
//  int index, num;
//  cin >> index >> num;
//  insert(l, index, num);
//  outputLink(l);

    cout << "创建新的链表\n";
    LinkList nL;
    initLink(nL);
    createLinkFromTail(nL);
    outputLink(nL);
    cout << "合并两个链表 \n";
    LinkList finalL;
    initLink(finalL);
    merge(l, nL, finalL);
    outputLink(finalL);

//  invert(l);
//  outputLink(l);
    return 0;
}

//初始化
void initLink(LinkList &l)
{
    //不带头结点的链表，那么这个指针就是链表的最后，所以初始值为空
    l = NULL;
}
//头插法创建链表
void createLinkFromHead(LinkList &l)
{
    int num;
    Node *newNode; 
    while (1)
    {
        cin >> num;
        if (num == -1)
        {
            break;
        }
        //按照输入的值创建一个结点
        newNode = new Node;
        newNode -> data = num;
        //结点指向头指针，头指针变成新建的结点，完成头插法
        newNode -> next = l;
        l = newNode;
    }
}
//尾插法创建链表
void createLinkFromTail(LinkList &l)
{
    Node *start = l,*newNode;
    int num;
    while (1)
    {
        cin >> num;
        if (num == -1)
        {
            break;
        }
        //按照传值新建结点，作为最后一个结点插入，所以他的指向都是空值
        newNode = new Node;
        newNode -> data = num;
        newNode -> next = NULL;

        if (start == NULL)//如果是初始值，那就把第一个点赋值给头指针
        {
            l = newNode;
            start = newNode;
        }
        else//不是第一个结点，那就让它指向下一个结点
        {
            start -> next = newNode;
            start = newNode;
        }
    }
}
//按照给定位置删除结点
void deleteNode(LinkList &l, int index)
{
    if (index <= 0)
    {
        cout << "输入位置错误" << endl;
        return;
    }
    Node *pre = l, *deleteNode;
    int count = 1;
    //删除，当删除第一个位置的时候，头指针就要向后移动一个结点，也就是改变了
    //头指针的值，所以使用引用参
    if (index == 1)
    {
        if (pre -> next)//还有后继结点，直接往后移动
        {
            l = pre -> next;
            delete pre;
        }
        else            //没有后继结点，直接为空
        {
            l = NULL;
        }
    }
    else
    {
        //普遍状况，直接找到前驱，删除要删除的结点，将前驱向后移动两个位置
        while ((pre -> next != NULL) && (count < index - 1))
        {
            pre = pre -> next;
            count++;
        }
        if (pre -> next == NULL)
        {
            cout << "删除位置出错"<< endl;
            return;
        }
        deleteNode = pre -> next;
        pre -> next = deleteNode -> next;
        delete deleteNode;
    }
}
//输出
void outputLink(LinkList l)
{
    if (l == NULL)
    {
        cout << "空链表，不支持输出" << endl;
        return ;
    }
    Node *start = l;
    //cout << start -> data << endl;
    while (start != NULL)
    {
        cout << start -> data << " ";
        start = start -> next;
    }
    cout << endl;
}
//求链表长度
int getLength(LinkList l)
{
    Node *start = l;
    int len = 0;
    while (start)
    {
        start = start -> next;
        len++;
    }
    return len;
}
//按值查找
Node * getUseData(LinkList l, int num)
{
    Node *start = l;
    while (start)
    {
        if (start -> data == num)
        {
            return start;
        }
        else
            start = start -> next;
    }
    return start;
}
//按位置查找
Node * getUseIndex(LinkList l, int index)
{
    Node *start = l;
    int count = 1;
    while (start)
    {
        if (count == index)
        {
            return start;
        }
        else
        {
            count++;
            start = start -> next;
        }
    }
    return start;
}
//插入
void insert(LinkList &l, int index, int data)
{
    if (index < 0)
    {
        cout << "插入位置无效\n";
        return ;
    }
    Node *newNode;
    if (index < 0)
    {
        cout << "输入位置错误\n";
        return ;
    }
    if (index != 1)
    {
        Node *pre = getUseIndex(l, index - 1);
        if (pre == NULL)
        {
            cout << "输入位置过大\n";
            return ;
        }
        else
        {
            newNode = new Node;
            newNode -> data = data;
            newNode -> next = pre -> next;
            pre -> next = newNode;
        }
    }
    else
    {
        newNode = new Node;
        newNode -> data = data;
        newNode -> next = l;
        l = newNode;
    }
}
//合并两个非递减链表
void merge(LinkList lA, LinkList lB, LinkList &lC)
{
    Node *aNextNode, *bNextNode, *cNextNode;
    lC = lA;//初始化，必须有，因为lC在初始化的时候是个空指针,
            //没有这一步，根本没法连接后面的结点
    aNextNode = lA;
    bNextNode = lB;
    cNextNode = lC;
    //开始为LC找到第一个结点
    if (aNextNode ->data <= bNextNode -> data)
    {
        cNextNode = aNextNode;
        aNextNode = aNextNode -> next;
    }
    else
    {
        cNextNode = bNextNode;
        bNextNode = bNextNode -> next;
    }
    //后面的结点按照有头指针的方法找就可以了
    while (aNextNode != NULL && bNextNode != NULL)
    {
        if (aNextNode -> data <= bNextNode -> data)
        {
            //cout <<"aNextNOde\n";
            cNextNode -> next = aNextNode;
            cNextNode = aNextNode;
            aNextNode = aNextNode -> next;
        }
        else
        {
            //cout <<"bNextNOde\n";
            cNextNode -> next = bNextNode;
            cNextNode = bNextNode;
            bNextNode = bNextNode -> next;
        }
    }
    if (aNextNode)
    {
        cNextNode -> next = aNextNode;
    }

    if (bNextNode)
    {
        cNextNode -> next = bNextNode;
    }
}
//逆置一个链表
void invert(LinkList &l)
{
    Node *p = l, *q;
    l = NULL;//改变了头指针的值，所以传引用参，初始值为NULL
    while (p)
    {
        q = p -> next;
        p -> next = l;
        l = p;

        p = q;
    }
}

//带头结点的循环单链表
#include<iostream>

using namespace std;

struct Node
{
    int data;
    Node * next;
};

typedef Node Node, *CLinkList;
//初始化循环链表
void initCLink(CLinkList &cL);
//头插法创建循环链表，只要将结点指针指向头结点的下一个就好
void createCLinkFromHead(CLinkList cL);
//尾插法创建循环链表，将最后一个结点的指针指向新的结点，新的结点指针域指向头结点
void createCLinkFromTail(CLinkList cL);
//按照给定位置删除结点
void deleteNode(CLinkList cL, int index);
//输出循环链表，终止只能是当前结点的指针域指向头结点
void outputCLink(CLinkList cL);
//求链表长度
int getLength(CLinkList cL);
//按值查找
Node * getUseData(CLinkList cL, int num);
//按位置查找
Node * getUseIndex(CLinkList cL, int index);
//插入，能找到就好插入
void insert(CLinkList cL, int index, int data);
//合并两个链表
CLinkList mergeNoSort(CLinkList cLA, CLinkList cLB);
//合并两个非递减链表，要求合并后仍然是非递减
void merge(CLinkList cLA, CLinkList cLB, CLinkList &cLC);
//逆置一个链表
void invert(CLinkList cL);

int main()
{
    int data, index;
    CLinkList cL;
    CLinkList cL2;
    CLinkList cL3;
    initCLink(cL2);
    initCLink(cL3);
    initCLink(cL);
    //createCLinkFromHead(cL);
    createCLinkFromTail(cL);
    outputCLink(cL);

    cout << "输入要查找数字的下标: ";
    cin >> index;
    Node *node = getUseIndex(cL, index);
    cout << (node == NULL ? 0 : node -> data) << endl;

    cout << "输入要查找的数字: ";
    cin >> data;
    Node *node1 = getUseData(cL, data);
    cout << (node1 == NULL ? 0 : node1 -> data) << endl;

    cout << "输入删除结点的下标:";
    cin >> index;
    deleteNode(cL, index);
    outputCLink(cL);

    cout << "长度为:" << getLength(cL) << endl;

    cout << "插入，输入下标，和数值：";
    cin >> index >> data;
    insert(cL, index, data);
    outputCLink(cL);

    cout << "再创建一个循环链表：";

    createCLinkFromTail(cL2);
    outputCLink(cL2);
    //cL3 = mergeNoSort(cL, cL2);
    merge(cL, cL2, cL3);
    outputCLink(cL3);
    invert(cL);
    outputCLink(cL);
    return 0;
}

//初始化循环链表
void initCLink(CLinkList &cL)
{
    cL = new Node;
    cL -> next = cL;
}

//头插法创建循环链表，只要将结点指针指向头结点的下一个就好
void createCLinkFromHead(CLinkList cL)
{
    Node *newNode;
    int num;
    bool input = true;
    while (input)
    {
        cin >> num;
        if (num == -1)
        {
            break;
        }

        newNode = new Node;
        newNode -> data = num;
        newNode -> next = cL -> next;
        cL -> next = newNode;
    }
}

//尾插法创建循环链表，将最后一个结点的指针指向新的结点，新的结点指针域指向头结点
void createCLinkFromTail(CLinkList cL)
{
    Node *rear, *newNode;
    rear = cL;
    int num;
    bool input = true;
    while (input)
    {
        cin >> num;
        if (num == -1)
        {
            break;
        }
//方法一
//      newNode = new Node;
//      newNode -> data = num;
//      newNode -> next = rear -> next;
//      rear -> next = newNode;
//      rear = newNode;
//方法二
        newNode = new Node;
        newNode -> data = num;
        rear -> next = newNode;
        rear = newNode;
    }
//方法二
        rear -> next = cL;
}

//按照给定位置删除结点
void deleteNode(CLinkList cL, int index)
{
    //还是一样找到前驱，删除前驱后的结点
    Node *pre = cL, *deleteNode;
    int count = 0;

    if (index < 0)
    {
        cout << "输入位置不合法\n";
        return ;
    }

    while ((pre -> next != cL) && count < index - 1)
    {
        pre = pre -> next;
        count++;
    }

    if (pre -> next == cL)
    {
        cout << "输入位置过大\n";
        return ;
    }

    deleteNode = pre -> next;
    pre -> next = deleteNode -> next;

    delete deleteNode;
}

//输出循环链表，终止只能是当前结点的指针域指向头结点
void outputCLink(CLinkList cL)
{
    Node *start = cL;
    while (start -> next != cL)
    {
        start = start -> next;
        cout << start -> data << " ";
    }
    cout << endl;
}

//求链表长度
int getLength(CLinkList cL)
{
    Node *start = cL;
    int len = 0;
    while (start -> next != cL)
    {
        start = start -> next;
        len++;
    }
    return len;
}
//按值查找
Node * getUseData(CLinkList cL, int num)
{
    Node *start = cL -> next;
    while (start != cL)
    {
        if (start -> data == num)
        {
            break;
        }
        else
            start = start -> next;
    }

    return (start == cL ? NULL : start);
}
//按位置查找
Node * getUseIndex(CLinkList cL, int index)
{
    Node *start = cL -> next;
    int count = 1;
    if (index <= 0)
    {
        cout << "输入位置有误\n";
        return NULL;
    }
    //每次只是遍历一遍链表，一旦链表到达最后一个就停止
    while ((start -> next != cL) && count < index)
    {
        count++;
        //cout << count;
        start = start -> next;
    }
    //但是停止的一整状况就是，仅仅是因为链表循环一遍结束而结束，此时count和index还没有匹配，
    //也就是说输入的下标太大了
    if ((start -> next == cL) && count < index)
    {
        cout << "输入位置下标越界\n";
        return NULL;
    }

    return start;
}
//插入，能找到就好插入
void insert(CLinkList cL, int index, int data)
{
    Node *pre = getUseIndex(cL, index - 1);
    if (pre == NULL || index < 0)
    {
        cout << "输入位置非法\n";
        return;
    }

    if (data < 0)
    {
        cout << "结点数值不能小于零\n";
        return ;
    }

    Node *newNode = new Node;
    newNode -> data = data;

    newNode -> next = pre -> next;
    pre -> next = newNode;
}
//合并两个链表
CLinkList mergeNoSort(CLinkList cLA, CLinkList cLB)
{
    Node *startA = cLA, *startB = cLB;
    while (startA -> next != cLA)
    {
        startA = startA -> next;
    }

    while (startB -> next != cLB)
    {
        startB = startB -> next;
    }

    startA -> next = cLB -> next;
    startB -> next = cLA;
    delete cLB;
    return cLA;
}
//合并两个非递减链表，要求合并后仍然是非递减
void merge(CLinkList cLA, CLinkList cLB, CLinkList &cLC)
{
    Node *aNextNode = cLA -> next, *bNextNode = cLB -> next, *cNextNode = cLC;
    cLC -> next = NULL;
    cLC = cLA;
    //这里的判断条件，可以满足每个链表的最后一个可以被考虑进去
    while ((aNextNode != cLA) && (bNextNode != cLB))
    {
        if (aNextNode -> data <= bNextNode -> data)
        {
            cNextNode -> next = aNextNode;
            cNextNode = aNextNode;
            aNextNode = aNextNode -> next;
        }
        else
        {
            cNextNode -> next = bNextNode;
            cNextNode = bNextNode;
            bNextNode = bNextNode -> next;
        }
    }
//  cout << aNextNode -> data << " " << bNextNode -> data << endl;
    while (aNextNode != cLA )
    {
        cNextNode -> next = aNextNode;
        cNextNode = aNextNode;
        aNextNode = aNextNode -> next;
    }

    while (bNextNode != cLB)
    {
        cNextNode -> next = bNextNode;
        cNextNode = bNextNode;
        bNextNode = bNextNode -> next;
    }

    cNextNode -> next = cLA;
    delete cLB;

}
//逆置一个链表
void invert(CLinkList cL)
{
    Node *nowNode = cL -> next, *nextNode;
    cL -> next = cL;//初始化
    while (nowNode != cL)
    {
        nextNode = nowNode -> next;
        nowNode -> next = cL -> next;
        cL -> next = nowNode;

        nowNode = nextNode;
    }
}