带头结点的单链表是指，在单链表的首元结点之前增加一个特殊的结点，称为头结点。
头结点的作用：使所有链表（包括空表）的头指针非空，并使对单链表的插入，删除操作不需要区分是否为空表或是否在第一个位置进行，从而与其他位置的插入，删除操作一致。

结构体

#include "seqlistlink.h"
#include <stdlib.h>
#include <assert.h>

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;
}

初始化

//初始化
void InitNodeList(pNode *pHead) {
    *pHead = (Node *)malloc(sizeof(Node));
    if(*pHead == NULL) {
        printf("申请空间失败...\n");
        return;
    }
    (*pHead)->next = NULL;
}

打印

//打印链表
void PrintNodeList(pNode head) {
    pNode p = head; //创建临时结点temp
    if (p == NULL) {
        printf("PrintNodeList---error...\n");
        return;
    }
    if (p->next == NULL) {
        printf("PrintNodeList---这是一个空表...\n");
        return;
    }
    p = p->next;
    while (p) {
        printf("%d\t", p->data);
        p = p->next;
    }
    printf("\n");
}

插入结点

//尾插
void InsertNodeBack(pNode *pHead, ElemType e) {
    assert(*pHead);
    pNode p = *pHead;
    pNode new = NewSpace(e);
    if(p->next == NULL) {
        p->next = new;
        new->next = NULL;
    }
    while (p->next != NULL) {
        p = p->next;
    }
    p->next = new;
    new->next = NULL;
}
//头插
void InsertNodeFront(pNode *pHead, ElemType e) {
    assert(*pHead);
    pNode p = *pHead;
    pNode next = p->next;
    pNode new = NewSpace(e);
    if (p->next == NULL) {
        p->next = new;
        new->next = NULL;
    }
    else {
        p->next = new;
        new->next = next;
    }
}
//指定位置插入
void InsertNodePos(pNode *pHead, ElemType data, int pos) {
    assert(*pHead);
    pNode p = (*pHead)->next;
    pNode new = NewSpace(data);
    if (p == NULL) {
        printf("InsertNodePos----这是一个空表...\n");
        return;
    }
    if (pos < 1) {
        printf("InsertNodePos插入位置错误...\n");
        return;
    }
    if (pos == 1) {
        (*pHead)->next = new;
        new->next = p;
    }
    else {
        for (int i=1; i<pos-1; i++) {
            p = p->next;
            if (p == NULL) {
                printf("InsertNodePos找不到，超过链表最大长度...\n");
                return;
            }
        }
        new->next = p->next;
        p->next = new;
    }
}

删除结点

//尾删
void RemoveNodeBack(pNode *pHead) {
    assert(pHead);
    pNode p = (*pHead)->next;
    if (p == NULL) {
        printf("RemoveNodeBack---Seqlist is Empty...\n");
        return;
    }
    if (p->next == NULL) {
        free(p);
        (*pHead)->next = NULL;
        printf("RemoveNodeBack---删除成功， 这是一个空表了...\n");
        return;
    }
    else {
        pNode pre = p;
        p = p->next;
        while (p->next != NULL) {
            pre = p;
            p = p->next;
        }
        pre->next = NULL;
        free(p);
    }
}
//首删
void RemoveNodeFront(pNode *pHead) {
    assert(pHead);
    pNode p = *pHead;
    if (p->next == NULL) {
        printf("RemoveNodeFront---Seqlist is Enpty...\n");
        return;
    }
    pNode del = p->next;
    if (del->next == NULL) {
        free(del);
        p->next = NULL;
        printf("RemoveNodeFront---这是一个空表了...\n");
        return;
    }
    else {
        p->next = del->next;
        free(del);
    }
}
//指定位置删除
void RemoveNodePos(pNode *pHead, int pos) {
    assert(pHead);
    pNode p = *pHead;
    pNode del = p->next;
    if (p->next == NULL) {
        printf("RemoveNodePos---这是一张空表...\n");
        return;
    }
    if (pos == 1) {
        p->next = del->next;
        free(del);
    }
    else {
        for (int i=1; i<pos; i++) {
            p = p->next;
            if(p->next == NULL) {
                printf("RemoveNodePos---找不到要删除的坐标，超过了最大长度...\n");
                return;
            }
        }
        del = p->next;
        p->next = del->next;
        free(del);
    }
}

查找元素位置

//查找元素位置
int FindNodePos(pNode *pHead, ElemType data) {
    assert(*pHead);
    pNode p = (*pHead)->next;
    if(p == NULL) {
        printf("FindNodePos---空链表...\n");
        return -1;
    }
    int count = 1;
    while (p) {
        if (p->data == data) {
            return count;
        }
        else {
            p = p->next;
            count ++;
        }
    }
    printf("FindNodePos---找不到...\n");
    return -1;
}

删除值为data的结点

//删除第一个值为data的结点
void RemoveNodeNode(pNode *pHead, ElemType data) {
    assert(*pHead);
    int pos = FindNodePos(pHead, data);
    if (pos != -1) {
        RemoveNodePos(pHead, pos);
    }
    else {
        return;
    }
}
//删除所有值为data的结点
void RemoveNodeDataAll(pNode *pHead, ElemType data) {
    assert(pHead);
    pNode pre = (*pHead)->next;
    if (pre == NULL) {
        printf("RemoveNodeDataAll---链表为空...\n");
        return;
    }
    pNode front = *pHead;
    while (1) {
        if (pre->data == data) {
            front->next = pre->next;
            free(pre);
            pre = front->next;
        }
        else {
            front = pre;
            pre = pre->next;
        }
        if (pre == NULL) {
            return;
        }
    }
}

计算链表长度

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

逆置

//链表逆置，一种比较简单的方法是将链表元素按照首插的方法插到新链中完成逆置
void ReverseNode1(pNode *pHead) {
    assert(pHead);
    pNode pre = (*pHead)->next;
    if (pre == NULL) {
        printf("ReverseNode1---链表为空...\n");
        return;
    }
    pNode new = NULL;
    while (pre) {
        pNode cur = pre;
        pNode temp = NewSpace(pre->data);
        temp->next = new;
        pre = pre->next;
        new = temp;
        free(cur);
    }
    (*pHead)->next = new;
}
//链表逆置，另一种比较简单的方法是将链表节点按照首插的方法插到新链中完成逆置
void ReverseNode2(pNode *phead) {
    assert(phead);
    pNode pre = (*phead)->next;
    pNode new = NULL;
    while (pre) {
        pNode cur = pre;
        pre = pre->next;
        cur->next = new;
        new = cur;
    }
    (*phead)->next = new;
}
//链表逆置
void ReverseNode3(pNode *phead) {
    assert(phead);
    pNode temp = (*phead)->next;
    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)->next = temp_pre;
}

拼接链表

//拼接C=A+B 新建结点值为pa->data或者pb->data，将pc的next指向new结点，pc=new；pa=pa->next或者pb=pb->next
void JointNodeNew(pNode *La, pNode *Lb, pNode *Lc) {
    assert(*La);
    assert(*Lb);
    assert(*Lc);
    pNode pa = (*La)->next;
    pNode pb = (*Lb)->next;
    pNode pc = *Lc;
    if (pa == NULL  && pb) {
        pc->next = pb;
        return;
    }
    if (pb == NULL && pa) {
        pc->next = pa;
        return;
    }
    while (pa && pb) {
        if (pa->data <= pb->data) {
            pNode next = pa->next;
            pNode new = NewSpace(pb->data);
            pc->next = new;
            pc= new;
            pa = next;
        }
        else {
            pNode next = pb->next;
            pNode new = NewSpace(pb->data);
            pc->next = new;
            pc= new;
            pb = next;
        }
    }
    while(pa) {
        pNode new = NewSpace(pa->data);
        pc->next = new;
        pc = new;
        pa = pa->next;
    }
    while(pb) {
        pNode new = NewSpace(pb->data);
        pc->next = new;
        pc = new;
        pb = pb->next;
}
//链接拼接 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)->next;
    pNode pb = (*Lb)->next;
    pNode temp = *La;
    pNode tmp = *Lb;
    if (pa && pb == NULL) {
        return;
    }
    if (pb && pa == NULL) {
        (*La)->next = pb;
        return;
    }
    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) {
        temp->next = pb;
    }
}

约瑟夫环

//约瑟夫环
void NodeJosephCycle(pNode *pHead, int k) {
    assert(pHead);
    pNode cur = (*pHead)->next;
    //第一步，先让链表构成环，即需要一个变量（tail）遍历至最后一个节点，
    //然后让最后一个结点的next指向*phead
    pNode tail = *pHead;
    while (tail->next != NULL) {
        tail = tail->next;
    }
    tail->next = (*pHead)->next;
    //第二步，让链表从起始地址进行查询，找到k的位置，然后删掉这个结点，
    //从该结点的下一个结点继续找K个位置，再次删掉，直到剩一个结点为止
    //cur是我们要删除的结点，用pre来标识cur的上一个位置。
    while (cur->next != cur) {
        pNode pre = NULL;
        for (int i=0; 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;
}

查找是否含有某一元素

//查找是否含有某一元素
int FindDataExit(pNode *head, int data) {
    assert(*head);
    pNode p = (*head)->next;
    if (p == NULL) {
        printf("链表为空...\n");
        return -1;
    }
    while (p) {
        if (p->data == data) {
            return 1;
        }
        else
            p = p->next;
    }
    return -1;
}

找出两个单链表的共同结点

//找出两个单链表的共同结点
void FindPublicNode(pNode *L1, pNode *L2, pNode *head) {
    pNode new = *head;
    pNode p1 = (*L1)->next;
    pNode p2 = (*L2)->next;
    while (p1) {
        while (p2) {
            if (p1->data == p2->data) {
                if (FindDataExit(&new, p1->data) == -1) {
                    InsertNodeBack(&new, p1->data);
                    p2 = p2->next;
                }
                else
                    p2 = p2->next;
            }
            else {
                p2 = p2->next;
            }
        }
        p2 = (*L2)->next;
        p1 = p1->next;
    }
}

倒数顺序查找

//查找倒数第k位置上的结点
int FindLastData(pNode head, int k) {
    assert(head);
    pNode p = head->next;
    int length = NodeLength(head);
    if (p == NULL) {
        printf("空链表...\n");
        return 0;
    }
    if (length-k < 0) {
        printf("找不到k位置的结点...\n");
        return 0;
    }
    for (int i=0; i<length-k; i++) {
        p = p->next;
    }
    int data = p->data;
    printf("%d\n", data);
    return 1;
}

//查找倒数第k位置上的结点-一次遍历完成
int search_k(pNode head, int k) {
    pNode p = head->next;
    pNode q = head->next;
    if (p == NULL) {
        printf("空表...\n");
        return 0;
    }
    for (int i=0; i<k; i++) {
        p = p->next;
        if (p == NULL) {
            printf("超出链表长度...\n");
            return 0;
        }
    }
    while (p) {
        p = p->next;
        q = q->next;
    }
    printf("%d\n", q->data);
    return 1;
}

测试

void testSeqlist() {
    Node list;
    pNode head = &list;
    InitNodeList(&head);
    pNode head2 = &list;
    InitNodeList(&head2);
    pNode head3 = &list;
    InitNodeList(&head2);
    pNode head4 = &list;
    InitNodeList(&head4);
    pNode head5 = &list;
    InitNodeList(&head5);
    InsertNodeBack(&head, 12);
    InsertNodeBack(&head, 15);
    InsertNodeFront(&head, 9);
    PrintNodeList(head);
    RemoveNodeBack(&head);
    PrintNodeList(head);
    RemoveNodeFront(&head);
    PrintNodeList(head);
    InsertNodePos(&head, 23, 2);
    PrintNodeList(head);
    RemoveNodePos(&head, 3);
    PrintNodeList(head);
    printf("%d\n", FindNodePos(&head, 12));
    RemoveNodeNode(&head, 34);
    PrintNodeList(head);
    InsertNodeBack(&head, 12);
    InsertNodeBack(&head, 15);
    InsertNodeFront(&head, 23);
    InsertNodeBack(&head, 30);
    InsertNodeBack(&head, 33);
    InsertNodeFront(&head, 23);
    InsertNodeBack(&head, 23);
    PrintNodeList(head);
    RemoveNodeDataAll(&head, 23);
    PrintNodeList(head);
    printf("%d\n", NodeLength(head));
    printf("ReverseNode1...\n");
    ReverseNode1(&head);
    PrintNodeList(head);
    ReverseNode2(&head);
    PrintNodeList(head);
//    ReverseNode3(&head);
//    PrintNodeList(head);
    InsertNodeBack(&head2, 12);
    InsertNodeBack(&head2, 15);
    InsertNodeFront(&head2, 9);
    InsertNodeBack(&head2, 20);
    InsertNodeBack(&head2, 33);
    InsertNodeFront(&head2, 4);
    InsertNodeBack(&head2, 45);
    printf("JointNodeNew...\n");
    PrintNodeList(head);
    PrintNodeList(head2);
    JointNodeNew(&head, &head2, &head3);
    PrintNodeList(head3);
    printf("JointNode...\n");
    PrintNodeList(head);
    PrintNodeList(head2);
    JointNode(&head, &head2);
    PrintNodeList(head);
//    printf("NodeJosephCycle...\n");
//    NodeJosephCycle(&head2, 5);
    printf("FindDataExit...\n");
    PrintNodeList(head3);
    printf("%d\n", FindDataExit(&head3, 33));
    InsertNodeBack(&head4, 12);
    InsertNodeBack(&head4, 15);
    InsertNodeBack(&head4, 29);
    InsertNodeBack(&head4, 33);
    InsertNodeBack(&head4, 45);
    InsertNodeBack(&head4, 50);
    InsertNodeBack(&head4, 54);
    printf("head4...\n");
    PrintNodeList(head4);
    printf("head2...\n");
    PrintNodeList(head2);
    FindPublicNode(&head2, &head4, &head5);
    PrintNodeList(head5);
    printf("head...\n");
    PrintNodeList(head);
    printf("length======%d\n", NodeLength(head));
    FindLastData(head, 13);
    search_k(head, 13);
}