0.大忌

1.更新到下一个链表

用head=head->next;而不是head=head->data;
另外：不要忘记更新！！读取完后就应该更新，不然直接TLE或者RuntimeError

2.以一个元素创建一个新列表时忘记返回newnode

严重的错误，不过估计编译器也会报错

3.使用head和tail的话不需要用malloc分配内存，直接赋值NULL

否则会超时

1.头文件与模型定义

1
2
3
4
5
6
7
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct Node{
    int data;
    struct Node* next;
}Node;

next不要写错，然后分号别忘，没有typedef为了方便可以自己弄个
结构体里面是指针，不要漏了 *号

2.创建链表元素

以data为一个整数为例：

可以按需求修改函数

 

1
2
3
4
5
6
 Node* Createnode(int x){
     Node* newnode=(Node*)malloc(sizeof(Node));
     newnode->data=x;
     newnode->next=NULL;
     return newnode;
 }

返回值不要漏掉！链表最容易漏掉这个，最好先写这个

新生成的链表下一个是NULL，便于后续操作指向下一链表

创建列表的动态内存分配还是要注意怎么写，能最后free一下最好就free一下吧。

3.输入输出

以单整数链表的输入输出为例子

1
2
3
4
5
6
7
8
//输出
void Printnode(Node* head){
    while(head!=NULL){
        printf("%d ",head->data);
        head=head->next;
    }
    printf("\n");
}

输出大差不差，有时会用->作为连接
下面看看输入：

1.scanf+getchar检测换行符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//输入
void Inputnode(void){
    int temp=0;
    Node* head=NULL;
    Node* tail=NULL;
    while(scanf("%d",&temp)==1){
        Node* newnode=Createnode(temp);
        if(head==NULL){
            head=tail=newnode;
        }
        else{
            tail->next=newnode;
            tail=newnode;
        }
    }
}

有一个问题是，必须输入一行后接上换行符

如果最后一行没有接上换行符就不行了

scanf不要漏掉换行符

2.fgets+strtok

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Node* Inputnode(void){
    char buffer[1024];//这里可以改，要多大有多大
    Node* head=NULL;
    Node* tail=NULL;
    if(fgets(buffer,sizeof(buffer),stdin)){
        char* token=strtok(buffer," ");
        while(token){
            int temp=atoi(token);
            Node* newnode=Createnode(temp);
            if(head==NULL){
                head=tail=newnode;
            }
            else{
                tail->next=newnode;
                tail=newnode;
            }
            token=strtok(NULL," ");
        }
    }
    return head;//一定要记得return
}

这个更加稳定（）

3.构建链表基本框架

1.设置头尾+自行判断

1
2
3
4
5
6
7
8
9
10
11
Node* head=NULL;
Node* tail=NULL;
Node* newnode=____;
if(head==NULL){
    head=tail=newnode;
}
else{
    tail->next=newnode;
    tail=newnode;
}
return head;

==注意相等是两个等号==

2.哑巴节点

指向头节点,可以不必判断头结点的特殊情况了

4.基本函数

链表函数基本上返回的都是指针，应该写Node*

插入链表元素

1
2
3
4
5
6
7
8
9
Node* insert(Node* head,Node* insert,int m){
	Node* p=head;
	for(int i=0;i<m-1;i++){//要看好插入的位置,此处插在右边
		p=p->next;
	}
	insert->next=p->next->next;
	p->next=insert;
	return head;
}

删除链表元素

此处为删除重复元素

先跳线，在炸掉桥，再把现在的由之前的来定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#define Max 100

void deleteDuplicates(struct Node* head){
	int* a=(int*)calloc(Max,sizeof(int));
	Node* pre=NULL;
    Node* curr=head;
    while(curr!=NULL){
        if(a[curr->data]==0){
            a[curr->data]=1;
		    pre=curr;
		    curr=curr->next;
	    }
        else if(a[curr->data]==1){
            pre->next=curr->next;  
            free(curr);
            curr=pre->next;            
        }
    }
    free(a);
}

整数链表合并函数(正序)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
Node* mergenode(Node* node1, Node* node2) {
    Node* p1 = node1;
    Node* p2 = node2;
    Node* head = NULL;
    Node* tail = NULL;
    while (p1 && p2) {
        Node* newnode;
        if (p1->data <=p2->data) {
            newnode = Createnode(p1->data);
            p1 = p1->next;
        }
        else {
            newnode = Createnode(p2->data);
            p2 = p2->next;
        }
        if (head == NULL) {
            head = tail = newnode;
        }
        else {
            tail->next = newnode;
            tail = newnode;
        }
    }

    if (p1 == NULL) {
        tail->next = p2;
    }
    else {
        tail->next = p1;
    }
    return head;
}

指定位置逆序

详细注释版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
Node* Inversenode(Node* node, int m, int n) {
    // 如果 m == n，表示区间不需要反转，直接返回原链表
    if (m == n) return node;
    // 创建一个哑结点（dummy node），用于简化链表边界处理
    // 哑结点的 next 指向链表的头部
    Node* dummy = (Node*)malloc(sizeof(Node));
    dummy->next = node;
    // pre 用于记录反转区间的前一个节点
	Node* pre = dummy;
	
    // 移动 pre 指针到反转区间的前一个节点，pre 就是反转区间前一个节点

    // 例如，如果 m=2，pre 最终会指向第一个节点

    for (int i = 1; i < m; i++) {
        pre = pre->next;  // 移动 pre 到第 m-1 个节点
    }

    // start 是反转区间的第一个节点，then 是 start 后面的节点（即第一个需要反转的节点）
    Node* start = pre->next;
    Node* then = start->next;
    // 反转区间内的节点
    // 通过改变指针顺序来完成反转。反转的范围是从 m 到 n
    // 反转 n - m 次
    for (int i = 0; i < n - m; i++) {
        // 步骤 1：start->next 指向 then->next，即跳过 then
        start->next = then->next;

        // 步骤 2：then->next 指向 pre->next，即将 then 放到反转区间的最前面

        then->next = pre->next;

        // 步骤 3：pre->next 指向 then，即把 pre 连接到 then 上

        pre->next = then;

        // 步骤 4：then 移动到下一个节点，准备进行下一次反转

        then = start->next;  // 重新指向 start 的下一个节点
    }

    // 返回新的链表头（dummy->next）
    Node* result = dummy->next;

    // 释放哑结点
    free(dummy);
    
    return result;
}

辅助理解动画：[终于把单链表反转搞明白了(一)_带头节点的单链表原地反转_哔哩哔哩_bilibili]

模板精简版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Node* Inversenode(Node* node,int m,int n){
    if(m==n) return node;
    Node* dummy=(Node*)malloc(sizeof(Node));
    dummy->next=node;
    Node* pre=dummy;
    for(int i=1;i<m;i++){
        pre=pre->next;
    }
    Node* start=pre->next;
    Node* then=start->next;
    for(int i=0;i<n-m;i++){
        start->next=then->next;
        then->next=pre->next;
        pre->next=then;
        then=start->next;
    }
    Node* res=dummy->next;
    free(dummy);
    return res;
}