单链表-不带头结点

链表，别名链式存储结构或单链表，用于存储逻辑关系为 "一对一" 的数据。与顺序表不同，链表不限制数据的物理存储状态，换句话说，使用链表存储的数据元素，其物理存储位置是随机的。

链表中数据元素的构成

每个元素本身由两部分组成：

• 本身的信息，称为“数据域”；
• 指向直接后继的指针，称为“指针域”。

这两部分信息组成数据元素的存储结构，称之为“结点”。n个结点通过指针域相互链接，组成一个链表。

typedef int ElemType;
typedef struct LinkNode
{
    ElemType data;
    struct LinkNode *next;
}Node,*pNode;

//为新节点开辟空间 这个一块存储空间 包括一个数据域+一个指针域
pNode NewSpace(ElemType data)
{
    pNode tmp = (Node *)malloc(sizeof(Node));
    tmp->data = data;
    tmp->next = NULL;
    return tmp;
}

头结点、头指针和首元结点

• 头结点：有时，在链表的第一个结点之前会额外增设一个结点，结点的数据域一般不存放数据（有些情况下也可以存放链表的长度等信息），此结点被称为头结点。若头结点的指针域为空（NULL），表明链表是空表。头结点对于链表来说，不是必须的，在处理某些问题时，给链表添加头结点会使问题变得简单。
• 首元结点：链表中第一个元素所在的结点，它是头结点后边的第一个结点。
• 头指针：永远指向链表中第一个结点的位置（如果链表有头结点，头指针指向头结点；否则，头指针指向首元结点）。

头结点和头指针的区别：头指针是一个指针，头指针指向链表的头结点或者首元结点；头结点是一个实际存在的结点，它包含有数据域和指针域。两者在程序中的直接体现就是：头指针只声明而没有分配存储空间，头结点进行了声明并分配了一个结点的实际物理内存。

单链表初始化

//初始化
void InitNodeList(pNode *pHead) {
    *pHead = NULL;
}

尾插

//尾插
void InsertNodeBack(pNode *pHead, ElemType e) {
    assert(NULL != pHead);
    pNode temp = *pHead; //创建临时结点temp
    //判断节点是否为空，如果为空就给让分配空间
    if (*pHead == NULL) {
        *pHead = NewSpace(e);
    }
    else {
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = NewSpace(e);
    }
}

首插

//头插
void InsertNodeFront(pNode *pHead, ElemType e) {
    assert(NULL != pHead);
    pNode temp; //创建临时结点temp
    temp = NewSpace(e);
    temp->next = *pHead;
    *pHead = temp;
}

尾删

//尾删
void RemoveNodeBack(pNode *pHead) {
    assert(NULL != pHead);
    pNode temp = *pHead;
    if (temp == NULL) {
        printf("Seqlist is Empty...\n");
        return;
    }
    else if (temp->next == NULL) {
        free(temp);
        *pHead = NULL;
    }
    else {
        temp = *pHead;
        pNode pre = NULL;
        while (temp->next != NULL) {
            pre = temp;
            temp = temp->next;
        }
        pre->next = NULL;
        free(temp);
        temp->next = NULL;
    }
}

首删

//首删
void RemoveNodeFront(pNode *pHead) {
    assert(pHead);
    pNode temp = *pHead;
    if (temp == NULL) {
        printf("Seqlist is Enpty...\n");
        return;
    }
    else if(temp->next == NULL) {
        *pHead = NULL;
        free(temp);
    }
    else {
        *pHead = temp->next;
        free(temp);
    }
}

删除指定位置节点

//指定位置删除
void RemoveNodePos(pNode *pHead, int pos) {
    assert(pHead);
    pNode pre = *pHead;
    if (pos == 1) {
        *pHead = pre->next;
        free(pre);
    }
    else {
        for (int i=1; i<pos-1; i++) {
            pre = pre->next;
            if(pre == NULL) {
                printf("找不到要删除的坐标，超过了最大长度...\n");
                return;
            }
        }
        pNode cur = pre->next;
        pre->next = cur->next;
        free(cur);
    }
}

在指定位置插入节点

//指定位置插入
void InsertNodePos(pNode *pHead, ElemType data, int pos) {
    assert(pHead);
    pNode pre = *pHead;
    if (pos == 1) {
        pNode temp = NewSpace(data);
        *pHead = temp;
        temp->next = pre;
        *pHead = temp;
    }
    else {
        for (int i=1; i<pos-1; i++) {
            pre = pre->next;
            if (pre == NULL) {
                printf("找不到，超足了链表最大长度...\n");
                return;
            }
        }
        pNode cur = NewSpace(data);
        cur->next = pre->next;
        pre->next = cur;
    }
}

删除链表中所有值为data的节点

//删除所有data的值
void RemoveNodeDataAll(pNode *pHead, ElemType data) {
    assert(pHead);
    pNode pre = *pHead;
    //只有一个元素并且值为要找的元素
    if (pre->data == data && pre->next == NULL) {
        free(pre);
        *pHead = NULL;
        return;
    }
    pNode cur = *pHead;
    while (1) {
        if (pre && pre->data == data && pre->next != NULL && pre->next->data != data) {
            *pHead = pre->next;
            free(pre);
            pre = *pHead;
        }
        while (pre && pre->data != data) {
            cur = pre;
            pre  = pre->next;
        }
        if (pre && pre->data == data && pre->next != NULL) {
            cur->next = pre->next;
            free(pre);
            pre = cur->next;
        }
        else if(pre && pre->data == data && pre->next != NULL) {
            cur->next = NULL;
            free(pre);
            pre = cur;
        }
        else {
            return;
        }
    }
}

获取节点长度

//计算链表长度
int NodeLength(pNode pHead) {
    assert(pHead);
    int count = 0;
    pNode pre = pHead;
    while (pre) {
        count ++;
        pre = pre->next;
    }
    return count;
}

打印

//打印链表
void PrintNodeList(pNode pHead) {
    assert(pHead);
    pNode temp = pHead; //创建临时结点temp
    while (temp != NULL) {
        printf("%d\t", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

逆置1

//逆置，从头到尾访问旧的链表，每访问一个，
//就将节点的数据采取头插的方式存入新的链表，释放原来链表的空间
void ReverseNode1(pNode *pHead) {
    assert(pHead);
    pNode pre = *pHead;
    pNode new = NULL;
    while (pre) {
        pNode cur = pre;
        pNode temp = NewSpace(pre->data);
        temp->next = new;
        pre = pre->next;
        new = temp;
        free(cur);
    }
    *pHead = new;
}

逆置2

//逆置，从头到尾访问旧的链表，每访问一个就把这个节点插到新的链表中
void ReverseNode2(pNode *phead) {
    assert(phead);
    pNode pre = *phead;
    pNode new = NULL;
    while (pre) {
        pNode cur = pre;
        pre = pre->next;
        cur->next = new;
        new = cur;
    }
    *phead = new;
}

逆置3

//链表逆置
void ReverseNode3(pNode *phead) {
    assert(phead);
    pNode temp = *phead;
    pNode temp_pre = NULL;
    pNode temp_next = NULL;
    if (temp->next == NULL) {
        return;
    }
    else if(temp->next->next == NULL) {
        return;
    }
    while (temp) {
        temp_next = temp->next;// 保存当前节点的下一个节点
        temp->next = temp_pre;//更新当前节点的指针域
        temp_pre = temp;//更新当前节点上一个节点的位置
        temp = temp_next;//更新当前节点的位置
    }
    *phead = temp_pre;
}

顺序表拼接1

//拼接C=A+B
void JointNodeNew(pNode *La, pNode *Lb, pNode *Lc) {
    pNode pa = *La;
    pNode pb = *Lb;
    pNode pc = *Lc;
    if (pa && pb == NULL) {
        *Lc = pa;
        return;
    }
    if (pb && pa == NULL) {
        *Lc = pb;
        return;
    }
    if (pb->data <= pa->data) {
        pNode temp = pb;
        pb = pb->next;
        *Lc = temp;
        pc = *Lc;
    }
    else if (pb->data > pa->data) {
        pNode temp = pa;
        pa = pa->next;
        *Lc = temp;
        pc = *Lc;
    }
    while (pa && pb) {
        if (pa->data <= pb->data) {
            pc->next = pa;
            pc= pa;
            pa = pa->next;
        }
        else {
            pc->next = pb;
            pc= pb;
            pb = pb->next;
        }
    }
    pc->next = pa?pa:pb;
}

顺序表拼接2

//链接拼接 A = A+B temp->next = pa
//pa->next = NULL 说明temp是最后一个元素， 只需要把Lb拼接到La
//temp->next = pb;
//使用一个tmp指向Lb的头节tmp=pb;
//当要把pb的节点拼接到La,首先把头节点只想pb的下一个节点tmp=pb->next
//把pb插入到La中之后，再把pb指向Lb的头节点tmp
void JointNode(pNode *La, pNode *Lb) {
    assert(La);
    assert(Lb);
    pNode pa = *La;
    pNode pb = *Lb;
    pNode temp = pa;
    pNode tmp = pa;
    if (pa && pb == NULL) {
        *La = pa;
    }
    else if (pb && pa == NULL) {
        *La = pb;
    }
    if(pb->data < pa->data) {
        tmp = pb->next;
        *La = pb;
        temp = pb;
        pb->next = pa;
        pb = tmp;
    }
    while (pa && pb) {
        if (pa->data > pb->data) {
            tmp = pb->next;
            temp->next = pb;
            pb->next = pa;
            temp = pb;
            pb = tmp;
        }
        else {
            temp = pa;
            pa = pa->next;
        }
    }
    if (pb == NULL) {
        return;
    }
    if (pb != NULL) {
        pa->next = pb;
    }
}

约瑟夫环

//约瑟夫环（约瑟夫问题）是⼀个数学的应⽤问题：
// 已知n个⼈（以编号1， 2， 3...n分别表⽰）围坐在⼀张//圆桌周围。
// 从编号为k的⼈开始报数，数到m的那个⼈出列；他的下⼀个⼈又从k开始报数，数到m的那个⼈
// 又出列；依此规律重复下去，直到圆桌周围的⼈全部出列
//约瑟夫环
void NodeJosephCycle(pNode *pHead, int k) {
    assert(pHead);
    pNode cur = *pHead;
    //第一步，先让链表构成环，即需要一个变量（tail）遍历至最后一个节点，
    //然后让最后一个结点的next指向*phead
    pNode tail = *pHead;
    while (tail->next != NULL) {
        tail = tail->next;
    }
    tail->next = *pHead;
    //第二步，让链表从起始地址进行查询，找到k的位置，然后删掉这个结点，
    //从该结点的下一个结点继续找K个位置，再次删掉，直到剩一个结点为止
    //cur是我们要删除的结点，用pre来标识cur的上一个位置。
    while (cur->next != cur) {
        pNode pre = NULL;
        int i=0;
        for (; i<k-1; i++) {
            pre = cur;
            cur = cur->next;
        }
        pre->next = cur->next;
        printf("delete....%d\n", cur->data);
        free(cur);
        cur = pre->next;
    }
    printf("save...%d\n", cur->data);
    cur->next = NULL;
}