C语言单链表的总结

文章目录

• • 初始节点结构：
  • 建链：
  • 插入：
  • • 尾插法：
    • 头插法：
  • 打印链表：
  • 删除节点：
  • 反转链表：
  • • 迭代法：
    • 递归法：
  • 完整代码（含输入输出）：

初始节点结构：

struct ListNode {
	int val;
	struct ListNode *next;
}

建链：

struct ListNode* createlist() {
	struct ListNode* Hnode = (struct ListNode*)malloc(sizeof(struct ListNode));申请内存空间，会用到stdlib.h头文件
	Hnode -> next = NULL;//初始化头节点
	return Hnode;
}

插入： 尾插法：

尾插法关键是需要一个实时记录尾部的一个尾指针俩进行插入，最后返回头list。

struct ListNode* insertNode(struct ListNode* list, int num); {
	int i;
	struct ListNode* tail = list;//创建一个尾指针
	for(i = 0; i < n; i++) {
		struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));//给新的节点申请内存
		scanf("%d", &node -> val);
		tail -> next = node;
		tail = tail -> next;//实现尾插 *** 作
	}
	return list;
}

头插法：

头插是让新的待插入的节点插到头节点的后面，每一个新的节点都是在之前节点的前面，在头节点的后面。

struct ListNode* insertNode(struct ListNode* list, int num); {
	int i;
	for(i = 0; i < n; i++) {
		struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));//给新节点申请内存
		scanf("%d", &node -> val);
		node -> next = list -> next;
		list -> next = node;//实现头插 *** 作
	}
	return list;
}

打印链表：

由于创建的头节点是没有赋val值的，所以说直接从头节点的下一个开始打印

void printList(struct ListNode* list) {
	struct ListNode* p = list -> next;
	//从头节点的下一节点打印
	while(p) {//判断p是否为空，等价于p  ！= NULL
		printf("%d ",p -> val);
		p = p->next;
	}
}

删除节点：

删除函数头部包含头节点指针和目标值两个参数

struct ListNode* deleteList(struct ListNode* head, int val) {
	struct ListNode* prev = (struct ListNode*)malloc(sizeof(struct ListNode));//由于可能会删除头节点，所以我们可以用一个哑节点prev来实现
	prev -> next = head;
	struct ListNode* p = prev;//用p -> next记录完成删除后的新的头节点
	while(prev != NULL && prev -> next != NULL) {
		if(prev -> next -> val == val) { //判断prev的下一个节点的val值是否为目标值
			prev -> next = prev -> next -> next;
		} else { //不是就跳到下一个节点继续判断
			prev = prev -> next;
		}
	}
	return p -> next;
}

反转链表： 迭代法：

用两个指针来记录curr前后的节点信息，一步步向后实现反转 *** 作

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* prev = NULL;//用prev和next来记录curr的前后节点
    struct ListNode* curr = head;
    while(curr){
        struct ListNode* next = curr -> next;//新的指针指向curr的下一个
        curr -> next = prev;当前节点的next指到前一个节点prev
        prev = curr;//向后继续遍历
        curr = next;
    }
    return prev;
}

递归法：

struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    struct ListNode* p = reverseList(head -> next);
    head -> next -> next = head;
    head -> next = NULL;
    return p;
}

完整代码（含输入输出）：

#include
#include
struct ListNode
{
	int val;
	struct ListNode* next;	
};


struct ListNode* createlist()
{
	struct ListNode* Hnode = (struct ListNode*)malloc(sizeof(struct ListNode));
	Hnode -> next = NULL;
	return Hnode;
}

struct ListNode* insertNode(struct ListNode* list, int num) {
	int i;
	struct ListNode* tail = list;
	for(i = 0; i < num; i++) {
		struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
		scanf("%d", &node -> val);
		node -> next = list -> next;
		list -> next = node;
	}
	return list;
}



void printlist(struct ListNode* list) {

	struct ListNode* p = list -> next;
	
	while(p) {
		printf("%d ",p -> val);
		p = p->next;
	}
}
struct ListNode* deleteList(struct ListNode* head, int val) {
	struct ListNode* prev = (struct ListNode*)malloc(sizeof(struct ListNode));
	prev -> next = head;
	struct ListNode* p = prev;
	while(prev != NULL && prev -> next != NULL) {
		if(prev -> next -> val == val) {
			prev -> next = prev -> next -> next;
		} else {
			prev = prev -> next;
		}
	}
	return p -> next;
}

int main(void)
{
	struct ListNode* list,* list1;
	int num;
	scanf("%d", &num);
	list = createlist();
	list1 = insertNode(list, num);
	printlist(list1);
	deleteList(list1, 3);
	printf("\n");
	printlist(list1);
	return 0;
}

输入：
5
1 3 5 7 9
（deleteList函数，删除val：3）
输出：