编程导航算法通关村第1关 | 单链表的基础与构造方法-Toy模板网

这篇具有很好参考价值的文章主要介绍了编程导航算法通关村第1关 | 单链表的基础与构造方法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1 单链表的基础与构造方法（C语言）

1.1 链表的结构

什么是链表
不强制要求数据在内存集中存储，可以分散存储在内存中。例如数据{1,8,6,2}，在链表的存储状态可能如图示：
只要让每一个元素知道它下一个元素的位置，就可以依次找出各个元素。
那么，链表是如何实现这种存储数据间的关系呢？为每一个元素配置一个指针，每个元素的指针指向自己的直接后继数据元素。通过指针建立数据连接关系。

1.2 链表的构建

链表组成
链表的”元素“由本身的数据信息和指针组成，标准定义如下图：

数据域用来存储元素的值。
指针域用来存放指针。
两部分构成的整体称为结点，也就是链表的基本单位。
也就是说，链表中实际存放的是一个一个的结点，
数据元素存放在各个结点的数据域中。如数据{1,8,6,2}，用链表存储可表示为：

链表中第一个结点的存储位置叫做头指针；
最后一个结点的指针为"空"，通常用NULL表示。
C语言代码实现链表创建

// 定义链表的结点
struct ListNode
{
    int val;               // 定义数据
    struct ListNode *next; // 定义指针，由于指针指向的是结构体的地址，所以定义指向结构体类型的指针变量
};

// 创建链表函数，返回指向结构体类型的指针变量
struct ListNode *initListNode()
{
    int i = 0;
    struct ListNode *head = NULL;                                 // 定义头指针
    struct ListNode *temp = (ListNode *)malloc(sizeof(ListNode)); // 定义第一个结点, temp 为第一个节点的地址  malloc返回值类型为(void *),所以用强制转换变为(ListNode *)类型
    temp->val = 0;                                                // 第一个节点的数据域赋初值
    temp->next = NULL;                                            // 给第一个节点的指针域赋初值
    head = temp;                                                  // 给头指针赋值
    for (i = 1; i < 10; i++)
    {
        struct ListNode *a = (ListNode *)malloc(sizeof(ListNode)); // 创建节点
        a->val = i;                                                // 给结点的数据域赋值
        a->next = NULL;                                            // 给结点的指针域赋初值
        temp->next = a;                                            // 将地址给到上一个结点的指针域
        temp = a;                                                  // 让temp指向下一个结点  也就是a节点的地址，能够将之后的节点赋值给到a节点的指针域
    }

    return head;
}

1.3 遍历链表

思路：只要知道链表的头指针地址，就可以获取第一个结点的数据域和指针域，当指针域的值不为空时，由于指针域为下一个结点的地址，就可以依次获取链表结点的值，直到获取的指针域为空时，表示已经到链表的最后一个结点，结束遍历。
通过遍历可以得到链表数据的值和链表长度。
C语言代码实现链表遍历获取值和长度

//打印链表的值
void PrintListNode(struct ListNode *p)
{
    struct ListNode *temp = p; // 定义一个循环的指针变量,把链表的头指针给到它
    while (temp)               // 当temp的值不等于NULL时，打印链表的值，空有2种情况，列表本身空的，打印无值，以及到了链表的最后一个结点
    {
        printf("%d ", temp->val); // 打印值
        temp = temp->next;        // 指向下一个结点的地址
    }
    printf("\n");
}

//获取链表的长度
int32_t getLength(struct ListNode *p)
{
    struct ListNode *temp = p; // temp指针用来遍历链表
    int32_t length = 0;
    // 只要temp指向结点的next值不是NULL，就执行输出语句。
    while (temp)
    {
        // struct ListNode* f = temp;//准备释放链表中的结点
        length++;
        temp = temp->next;
        // free(f);
    }
    return length;
}

输出结果
编程导航算法通关村第1关 | 单链表的基础与构造方法,算法,链表,c语言

1.4 链表的插入

单链表的插入要考虑3种情况：首部、中部、尾部。
链表表头插入
新结点比较简单，容易出错的是经常忘记把head需要重新指向表头。创建一个新结点后，执行newNode ->next =
head，就可以链接原来的链表；之后，执行 head = newNode，把头指针重新指向表头即可，如下图：

链表中间插入
在中间位置，要先遍历找找到要插入的位置（如值为8的第三个结点位置），然后将当前结点接入到前驱结点和后继结点之间，但是到该位置后我们却不能获得前驱结点了，也就无法将结点接到前面去。这就好比是一边过河一边拆桥，结果自己也回不去了。
为此，我们需要在目标结点的前一个位置停下来，使用cur->next的值而不是cur的值来判断，这是链表最常用的策略。
例如下图中，如果要在第三个结点（值为8的位置）的前面插入，当cur->next = node（8）就应该停下，此时cur->val =
1,然后需要给newNode前后接2根线，此时只能先让newNode->next =
cur->next（图中虚线），然后cur->next = newNode,而且顺序不能颠倒。
为什么顺序不能颠倒？
由于每一个结点只有一个next，因此执行了cur->next =
newNode后，结点Node（1）和Node（8）的连接就断了，所以不能颠倒。
链表尾部插入
将尾结点指向新结点
C语言实现链表插入

/*
 链表插入
 head：待插入的链表
 nodeInsert： 插入结点
 position：插入位置 
*/
struct ListNode *insertNode(struct ListNode *head, struct ListNode *nodeInsert, int32_t position)
{
    if (head == NULL) // 待插入链表为空，可以认为待插入结点就是链表的头结点，也可以抛出不能插入的异常
    {
        nodeInsert->next = NULL;
        return nodeInsert;
    }

    int32_t len = getLength(head);
    if ((position < 1) || (position > (len + 1))) //插入位置限制，如果待插链表有2个结点，那么插入位置可以为1、2、3，其他位置非法
    {
        printf("插入位置非法");
    }
    if (position == 1)
    {
        nodeInsert->next = head;
        head = nodeInsert;
        return head;
    }
    struct ListNode *pNode = head;
    int count = 1; // 判断插入结点的前一个位置
    // if (count != position - 1)
    while (count < position - 1)
    {
        pNode = pNode->next;
        count++;
    }
    nodeInsert->next = pNode->next;
    pNode->next = nodeInsert;

    return head;
}

输出结果
编程导航算法通关村第1关 | 单链表的基础与构造方法,算法,链表,c语言

1.5 链表的删除

链表的删除同样分为删除头部元素，中部元素和尾部元素三部分。
删除头部结点元素
把头指针指向后一个结点，执行 head = head->next 就行。如下图示，将head向前移动一次之后，原来的结点不可达，然后就可以将其删除。
删除尾部结点元素
找到要删除元素的前驱结点，这里同样要在提前一个位置判断，例如下图中，删除值为2的结点，其前驱结点是值为1的结点，遍历的时候需要判断cur->next是否为2，如果是，则只要执行cu->next = NULL即可，此时值为2的结点就可以删掉了。
删除中间结点元素
删除中间结点时，也用cur->next进行比较，找到位置后，将cur->next指针的值更新为cur->next->next ,然后就可以放新删除中间值为1的结点，如下图示：
C语言实现

/*
 链表删除
 head：待插入的链表
 position：插入位置
*/
struct ListNode *deleteNode(struct ListNode *head, int32_t position)
{
    if (head == NULL) // 待插入链表为空，可以认为待插入结点就是链表的头结点，也可以抛出不能插入的异常
    {
        return NULL;
    }

    int32_t len = getLength(head);
    if ((position < 1) || (position > len))
    {
        printf("删除位置非法\n");
        return head;
    }
    if (position == 1)
    {
        struct ListNode *temp = head;
        head = head->next;
        free(temp);
        return head;
    }
    else
    {
        struct ListNode *curNode = head;
        int count = 1; // 判断插入结点的前一个位置
        // if (count != position - 1)
        while (count < position - 1)
        {
            curNode = curNode->next;
            count++;
        }
        struct ListNode *deleteNode = curNode->next;
        curNode->next = curNode->next->next;
        free(deleteNode);
        return head;
    }
}