数据结构：单链表

SList.h

#pragma once
#include
#include
#include

typedef int SLTDataType;

typedef struct SListNode {
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

void SLTPrint(SLTNode* phead);

SLTNode* BuySListNode(SLTDataType x);

void SLTPushBack(SLTNode** pphead,SLTDataType x);
void SLTPushFront(SLTNode** pphead,SLTDataType x);

void SLTPopFront(SLTNode** pphead);
void SLTPopBack(SLTNode** pphead);

SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
void SLTInsertAfter(SLTNode* pos, SLTDataType x);

void SLTErase(SLTNode** pphead, SLTNode* pos);

void SLTEraseAfter(SLTNode* pos);
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

SList.c

#include"SList.h"

void SLTPrint(SLTNode* phead) {
	SLTNode* cur = phead;
	while (cur) {
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

SLTNode* BuySListNode(SLTDataType x) {
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL) {
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

void SLTPushFront(SLTNode** pphead, SLTDataType x) {
	SLTNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

void SLTPushBack(SLTNode** pphead,SLTDataType x){
	
	assert(pphead);

	SLTNode* newnode = BuySListNode(x);

	if (*pphead == NULL) {
		*pphead = newnode;
	}
	else {
		SLTNode* tail = *pphead;
		while (tail->next != NULL) {
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

void SLTPopFront(SLTNode** pphead) {
	assert(*pphead);
	SLTNode* newhead = (*pphead)->next;
	free(*pphead);
	*pphead = newhead;
}

void SLTPopBack(SLTNode** pphead) {
	assert(*pphead);
	if ((*pphead)->next == NULL) {
		free(*pphead);
		*pphead = NULL;
	}
	else {
		SLTNode* tail = *pphead;
		while (tail->next->next) {
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {
	SLTNode* cur = phead;
	while (cur) {
		if (cur->data == x) {
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {
	assert(pos);
	if (pos == *pphead) {
		SLTPushFront(pphead, x);
	}
	else {
		SLTNode* prev = *pphead;
		while (prev->next != pos) {
			prev = prev->next;
		}
		SLTNode* newnode = BuySListNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

void SLTInsertAfter(SLTNode* pos, SLTDataType x) {
	assert(pos);
	SLTNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

void SLTErase(SLTNode** pphead, SLTNode* pos) {
	assert(pos);
	if (pos == *pphead) {
		SLTPopFront(pphead);
	}
	else {
		SLTNode* prev = *pphead;
		while (prev->next != pos) {
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		//pos = NULL;
	}
}

void SLTEraseAfter(SLTNode* pos) {
	assert(pos);
	assert(pos->next);
	SLTNode* posNext = pos->next;
	pos->next = posNext->next;
	
	free(posNext);
	posNext = NULL;
}
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

请添加图片描述
删除有序数组中的重复项

int removeDuplicates(int* nums, int numsSize){
    int begin = 0;
    int end = 0;
    // 0,0,1,1,1,2,2,3,3,4
//begin        0
//end                    1 
    while(end<numsSize){
        if(nums[end] == nums[begin]){
            // nums[begin] = nums[end];
            end++;
        }else{
            begin++;
            nums[begin] = nums[end];
            // end++;
        }
    }
    return begin+1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

反转链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* n1;
    struct ListNode* n2;
    struct ListNode* n3;
    n1 = NULL;
    n2 = head;
    if(n2)
        n3 = n2->next;
    
    while(n2!=NULL){
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if(n3)
            n3 = n3->next;
    }
    return n1;
}
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

移除链表元素

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode* prev = NULL,*cur = head;
    while(cur){
        if(cur->val == val){
            //删除
            if(cur == head){
                head = cur->next;
                free(cur);
                cur = head;
            }else{
                prev->next = cur->next;
                free(cur);
                cur = prev->next;
            }
        }else{
            prev = cur;
            cur = cur->next;
        }
    }
    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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode* cur = head;

    struct ListNode* newhead = NULL;
    struct ListNode* tail = NULL;

    while(cur){
        if(cur->val == val){
            //删除
            struct ListNode* del = cur;
            cur = cur->next;
            free(del);
        }else{
            //尾插
            if(tail == NULL){
                newhead = tail = cur;
            }else{
                tail->next = cur;
                tail = tail->next;
            }
                cur = cur->next;
        }
    }
    if(tail)
        tail->next = NULL;
    return newhead;
}
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

链表的中间结点(快慢指针)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while(fast && fast->next){
        slow = slow -> next;
        fast = fast->next->next;   
    }
    return slow;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

合并两个有序链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    if(list1 == NULL)
        return list2;
    if(list2 == NULL)
        return list1;
        
    struct ListNode* newhead = NULL;
    struct ListNode* tail = NULL;

    while(list1 && list2){
        if(list1->val<list2->val){
            if(newhead == NULL){
                newhead = tail = list1;
            }else{
                tail->next = list1;
                tail = tail->next;
            }
            list1 = list1->next;
        }else{
            if(newhead == NULL){
                newhead = tail = list2;
            }else{
                tail->next = list2;
                tail = tail->next;
            }
            list2 = list2->next;
        }
    }
    if(list1)
        tail->next = list1;
    if(list2)
        tail->next = list2;
    return newhead;
}
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

链表中倒数第k个结点

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

/**
 * 
 * @param pListHead ListNode类 
 * @param k int整型 
 * @return ListNode类
 */
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    struct ListNode* slow = pListHead;
    struct ListNode* fast = pListHead;

    //先让fast指针走k步
    while(k--)
    {
        // 链表都没有k步长，那么倒数第k就是空
        if(fast == NULL)
            return NULL;
        fast = fast->next;
    }

    //再让slow和fast一起走
    //当fast为空的时候结束循环
    while(fast!=NULL)
    {
        slow = slow->next;
        fast =  fast->next;
    }

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

反转链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* cur = head;
    struct ListNode* newhead = NULL;

    while(cur){ 
        struct ListNode* next = cur->next;

        //头插
        cur->next = newhead;
        newhead = cur;
        cur = next;
    }
    return newhead;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

合并两个有序链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    if(list1 == NULL)
        return list2;    
    if(list2 == NULL)
        return list1;
    
    struct ListNode* head = NULL;
    struct ListNode* end = NULL;
	带一个头结点 方便尾插
    head = end = (struct ListNode*)malloc(sizeof(struct ListNode));

    while(list1 && list2){
        if(list1->val<list2->val){
            end->next = list1;
            end = end->next;
            list1 = list1->next;        
        }else{
            end->next = list2;
            end = end->next;
            list2 = list2->next;
        }
    }
    if(list1){
        end->next = list1;
    }
    if(list2){
        end->next = list2;
    }
    struct ListNode* del = head;
    head = head->next;
    free(del);

    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

链表分割

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
#include 
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
    //first 是小于
    //second 是大于
        struct ListNode * firstbegin = NULL;
        struct ListNode * firstend = NULL;
        
        struct ListNode * secondbegin = NULL;
        struct ListNode * secondend = NULL;

    //1 两部分的头尾指针要指向同一个头结点
        firstbegin = firstend = (struct ListNode *)malloc(sizeof(struct ListNode));
        secondbegin = secondend = (struct ListNode *)malloc(sizeof(struct ListNode));

        struct ListNode * current = pHead;

        while(current!=NULL){
            if(current->val<x){
                firstend->next = current;
                firstend = firstend ->next;
            }else{
                secondend->next = current;
                secondend = secondend ->next;                
            }
            current = current ->next;
        }
    //2 将第一部分的end的next去连接上第二部分的begin的next
        firstend->next = secondbegin->next;
    //3 为了避免环（secondend的next为NULL）
        secondend->next = NULL;
        struct ListNode * newhead = firstbegin->next;
        free(firstbegin);
        free(secondbegin);
        return newhead;
    }
};
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

回文链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode * middle(struct ListNode* head){
    struct ListNode * fast = head;
    struct ListNode * slow = head;

    while(fast && (fast->next)){
        //奇数结点：5
        //1 2 3 4 5
        //fast 1 3 5 fast->next为空
        //slow 1 2 3（3是中间结点）
        //偶数结点：4
        //1 2 3 4
        //fast 1 3 NULL
        //slow 1 2 3（3是中间结点）
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

struct ListNode *reverse(struct ListNode* middle_node){
    //1 2 2 1
    //2 1
    //1 2
    struct ListNode *newhead = NULL;
    struct ListNode *curhead = middle_node;

    while(curhead!=NULL){
        struct ListNode* next = curhead->next;
        curhead->next = newhead;
        newhead = curhead;
        curhead = next;
    }
    return newhead;
}

bool isPalindrome(struct ListNode* head){
    //第一步找到中间结点
    //第二步使用中间结点去逆序第二个子链表
    //第三步将两个链表去进行比较
    struct ListNode * middle_node = middle(head);
    struct ListNode *reverse_node = reverse(middle_node);

    while(head && reverse_node){
        if(head->val != reverse_node->val){
            return false;
        }else{
            head = head->next;
            reverse_node = reverse_node->next;
        }
    }
    return true;
}
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
50
51
52
53
54
55
56
57
58
59
60

相交链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode * testa = headA;
    struct ListNode * testb = headB;

    //先去计算一下两个链表的长度
    int lena = 0;
    int lenb = 0;

    while(testa!=NULL){
        testa = testa->next;
        lena++;
    }
    
    while(testb!=NULL){
        testb = testb->next;
        lenb++;
    }

    int lensum = abs(lena-lenb);

    struct ListNode * longnode = headA;
    struct ListNode * smartnode = headB;

    if(lena<lenb){
        longnode = headB;
        smartnode = headA;
    }

    while(lensum--){
        longnode = longnode->next;
    }

    while(longnode != smartnode){
        longnode = longnode->next;
        smartnode = smartnode->next;
    }
    return longnode;
}
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

环形链表1

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) {
    struct ListNode* slow = head;
    struct ListNode* fast = head;

    // 奇数结点 与 偶数结点 两种情况
    while(fast && fast->next){
        //奇数结点：5
        //1 2 3 4 5
        //slow 1 2 3
        //fast 1 3 5
        //fast的next为NULL
        slow = slow->next;
        fast = fast->next->next;
        //偶数结点：4
        //1 2 3 4 
        //slow 1 2 3
        //fast 1 3 NULL
        //fast为NULL
        if(slow == fast)
            return true;
    }
    return false;
}
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

环形链表2

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* m = head;
    struct ListNode* k = head;

    while((k!=NULL)&&(k->next!=NULL))
    {
        m = m->next;
        k = k->next->next;

        if(m == k)
        {
            struct ListNode* meet = m;
            while(head!=meet)
            {
                head = head->next;
                meet = meet->next;
            }
            return meet;
        }
    }
    return NULL;
}
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

复制带随机指针的链表

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */

struct Node* copyRandomList(struct Node* head) {
    //1 将每个 拷贝节点 都 插入 在原来的节点的后面
    struct Node* cur = head;
    while(cur){
        struct Node* next = cur->next;
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        //拷贝结点的值和cur的值相同
        copy->val = cur->val;

        //将拷贝结点插入在cur的后面
        cur->next =copy;
        copy->next = next;

        //往后走
        cur = next;
    }

    //2 链接每个拷贝结点的 random
    cur =  head;
    while(cur){
        struct Node* copy = cur->next;

        //链接random
        if(cur->random == NULL)
            copy->random = NULL;
        else
            copy->random = cur->random->next;//注意

        cur = copy->next;
    }

    //3 将拷贝结点 解 下来，尾插到一起，恢复原来链表。
    cur = head;
    struct Node* copyhead = NULL;
    struct Node* copytail = NULL;
    while(cur){
        struct Node* copy = cur->next;
        struct Node* next = copy->next;

        //最开始为空
        if(copytail == NULL)
            copyhead = copytail = copy;
        else{
            copytail->next = copy;
            copytail = copytail->next;
        }

        //恢复原来的链表
        cur->next = next;
        //注意
        cur = next;
    }
    return copyhead;
}
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63

相关阅读:
前端开发：JS中==和===的对比总结
 雅可比矩阵和雅可比坐标
 如何在移动端猎豹浏览器中设置代理IP
docker单机安装Higress（踩坑+解决）
Flink SQL Window TopN 详解
 Mybatis-plus多数据源单元测试@MybatisPlusTest
first-order-model实现照片动起来（附工具代码） | 机器学习
 .NET基础面试题
 JDBC 访问数据库
 Linux服务：Nginx反向代理与负载均衡
原文地址：https://blog.csdn.net/qq_62552630/article/details/133364532