单链表相关OJ题（LeetCode、C语言、数据结构）

前言：

在学习完链表部分（主要是单链表）相关函数，包括头插、头删、尾插、尾删等函数接口的实现思想，通过下面11道OJ题继续巩固知识。
数据结构主要学习其管理数据的方法思想，掌握他们处理数据的思想即可。
题目来源：LeetCode、牛客
实现：C语言
做题技巧：

画图，分析代码逻辑，走读代码分析
画图，手搓链表，VS调试

. 题目链接如下：

移除链表元素
反转链表
链表的中间结点
链表中倒数第k个结点
合并两个有序链表
链表分割
链表的回文结构
相交链表
环形链表
环形链表 II
复制带随机指针的链表

1. 移除链表元素

LeetCode链接：移除链表元素

1.1 题目描述

要求：给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回新的头节点。

1.2 解决思路

思路一：双指针

一般情况

使用双指针，一个cur，赋初值head，一个prev赋初值NULL，用cur遍历，直到cur==NULL结束
若cur->val != val，则先把cur的值赋给prev，再让cur往下走；若cur->val == val，则先操作prev->next = cur->next,完成链接后，free掉cur结点，在把prev->next赋值给cur（双指针迭代往后走）
重复2步骤，直到cur完成遍历

头删情况

最开始，如果cur->val == val，头删，更新head，先让head往后走，free掉cur，在让cur=head
继续判断

注意：这道题的头删没有使用二级指针，因为该函数带返回值。

思路二：遍历原链表，把不是val的结点拿出来进行尾插到新链表，再返回新链表的头

尾插效率较低，使用一个tail指针，赋初值NULL，标记尾巴，提高找尾效率
用cur指针遍历原链表，赋初值head
把不是val的结点依次尾插到tail->next,若是val的结点，则用一个指针del标记cur结点，先让cur往后走，再free是该结点
最后的tail->next赋值NULL（否则尾删情况会有野指针）
头删情况：最开始，把head赋值给cur之后，要置空，赋值NULL

思路三：在思路二的基础上改进，增加一个哨兵位的头结点，哨兵位是尾插时考虑**

1.3 AC代码

思路一：

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

	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
31
32
33

思路二：

struct ListNode* removeElements(struct ListNode* head, int val){
	struct ListNode* cur = head;
	struct ListNode* tail = NULL;
	head = NULL;
    
	while (cur)
	{
		if (cur->val == val)
		{
			struct ListNode* del = cur;
			cur = cur->next;
			free(del);
		}
		else
		{
			//尾插
			if (tail == NULL)
			{
				head = tail = cur;
			}
			else
			{
				tail->next = cur;
				tail = tail->next;
			}

			cur = cur->next;
		}
	}

	if(tail)
		tail->next = NULL;

	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

思路三：

struct ListNode* removeElements(struct ListNode* head, int val) {
	struct ListNode* cur = head;
	struct ListNode* tail = NULL;
	//哨兵位节点
	head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
	tail->next = NULL;
	while (cur)
	{
		if (cur->val == val)
		{
			struct ListNode* del = cur;
			cur = cur->next;
			free(del);
		}
		else
		{
			//尾插
			tail->next = cur;
			tail = tail->next;

			cur = cur->next;
		}
	}
	tail->next = NULL;

	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

2. 反转链表

LeetCode链接：反转链表

2.1 题目描述

要求：逆置单链表

2.2 解决思路

思路一：使用头插思路，头插不需要考虑哨兵位，哨兵位是尾插时考虑

思路二：把指针的方向颠倒，空链表直接返回NULL

迭代过程：

n2->next = n1（倒指向）
n1 = n2
n2 = n3
n3 = n3->next（当n3 != NULL时才可操作）
结束条件：n2 == NULL

2.3 AC代码

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

	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

3. 链表的中间结点

LeetCode链接：链表的中间结点

3.1 题目描述

要求： 只能遍历链表一遍，返回链表中间节点

3.2 解决思路

使用快慢指针

3.3 AC代码

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

4. 链表中倒数第k个结点

牛客链接：链表中倒数第k个结点

4.1 题目描述

要求： 找倒数第k个结点

4.2 解决思路

使用快慢指针，让快指针先走K步，然后快慢指针同时走，快指针走到尾巴时，慢指针刚好是倒第k个结点

注意：当k大于链表长度，则不存在倒数第k个结点

4.3 AC代码

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    struct ListNode* slow, * fast;
    slow = fast = pListHead;
    //fast先走k步
    while (k--)
    {
        if (fast == NULL)//k比链表长度大，没有倒数第K个
        {
            return NULL;
        }
 
        fast = fast->next;
    }
    //再同时走
    while (fast)
    {
        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

5. 合并两个有序链表

LeetCode链接：合并两个有序链表

5.1 题目描述

要求：合并两个升序链表成一个新的升序链表，返回新链表

5.2 解决思路

利用归并排序思想，从头比较，取小的尾插到新链表

注意：

尾插效率低，要定义一个tail指针，标记链表尾巴

5.3 AC代码

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    if (list1 == NULL)
		return list2;
	if (list2 == NULL)
		return list1;

	struct ListNode* head, * tail;
	head = tail = NULL;

	while (list1 && list2)
	{
		if (list1->val < list2->val)
		{
			if (tail == NULL)
			{
				head = tail = list1;
			}
			else
			{
				tail->next = list1;
				tail = tail->next;
			}

			list1 = list1->next;
		}
		else
		{
			if (tail == NULL)
			{
				head = tail = list2;
			}
			else
			{
				tail->next = list2;
				tail = tail->next;
			}

			list2 = list2->next;
		}
	}

	if (list1)
		tail->next = list1;

	if (list2)
		tail->next = list2;

	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

6. 链表分割

牛客链接：链表分割

6.1 题目描述

要求：编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前，返回重新排列后的链表的头指针。

6.2 解决思路

定义两个新链表，都带哨兵位

注意：

分析极端场景：想极端场景

都比x小
都1比x大
有大有小

6.3 AC代码

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        struct ListNode* greaterhead, *greatertail, *lesshead, *lesstail;
        greaterhead = greatertail = (struct ListNode*)malloc(sizeof(struct ListNode));
        lesshead = lesstail = (struct ListNode*)malloc(sizeof(struct ListNode));
        greatertail->next = NULL;
        lesstail->next = NULL;
        
        struct ListNode* cur = pHead;
        while(cur)
        {
            if(cur->val < x)
            {
                lesstail->next = cur;
                lesstail = lesstail->next;
            }
            else
            {
                greatertail->next =cur;
                greatertail = greatertail->next;
            }
            
            cur = cur->next;
        }

        lesstail->next = greaterhead->next;
        greatertail->next = NULL;
        
        struct ListNode* head = lesshead->next;
        free(greaterhead);
        free(lesshead);
        
        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

7. 链表的回文结构

牛客链接：链表的回文结构

7.1 题目描述

要求：时间复杂度O(n)，空间复杂度O(1)

7.2 解决思路

注意：这种方法属于侵入式编程，破坏了源链表的结构，如果题目有要求，要恢复回去，当然这题没有要求，可不用管。

7.3 AC代码

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    //调用以前写的链表找中间节点
    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;
}
    
    //调用以前写到逆置链表
    struct ListNode* reverseList(struct ListNode* head) {
	if (head == NULL)
		return NULL;

	struct ListNode* n1, * n2, * n3;
	n1 = NULL;
	n2 = head;
	n3 = n2->next;

	while (n2)
	{
		//倒指向
		n2->next = n1;
		//迭代
		n1 = n2;
		n2 = n3;
		if (n3)
		{
			n3 = n3->next;
		}
	}

	return n1;
}
    
    //判断回文部分
    bool chkPalindrome(ListNode* A) {
        struct ListNode* head = A;
        struct ListNode* mid = middleNode(head);
        struct ListNode* rhead = reverseList(mid);
        
        while(head && rhead)
        {
            if(head->val != rhead->val)
            {
                return false;
            }
            else
            {
                head = head->next;
                rhead = rhead ->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
61
62
63
64
65
66
67
68
69
70

8. 相交链表

LeetCode链接：相交链表

8.1 题目描述

要求：时间复杂度O(n)，空间复杂度O(1)

8.2 解决思路

思路一：暴力对比，比较结点的地址，遍历A链表中的结点，与B链表中的每一个结点进行比较，这里比较的是地址

时间复杂度：O(n^2)
空间复杂度：O(1)

思路二：先判断相交，找尾结点，相交链表尾结点必定相等。相交的后半部是A和B相同的尾巴（后缀是相等的，相差在前面，先走差距步，相当于从同一起点走）

8.3 AC代码


struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* curA = headA, *curB = headB;
    int lenA = 1, lenB = 1;

    while(curA->next)
    {
        curA = curA->next;
        lenA++;
    }

    while(curB->next)
    {
        curB = curB->next;
        lenB++;
    }

    if(curA != curB)//尾节点，无交点的情况
    {
        return NULL;
    }
    //走到这里，必定有交点

    //求第一个交点
    struct ListNode* shortlist = headA,* longlist = headB;
    if(lenA > lenB)
    {
        shortlist = headB;
        longlist = headA;
    }

    int gap = abs(lenA - lenB);//求绝对值

    //长的先走gap步
    while(gap--)
    {
        longlist = longlist->next;
    }
    //同时走
    while(shortlist != longlist)
    {
        shortlist = shortlist->next;
        longlist = longlist->next;
    }

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

9. 环形链表

LeetCode链接：环形链表

9.1 题目描述

要求：空间复杂度O(1),判断是否带环，返回bool值

9.2 解决思路

带环链表的结构

注意：带环链表一遍历就会死循环

思路：使用快慢指针，转换成龟兔赛跑，追及问题。慢指针一次走一步，快指针一次走两步，如果带环，当快慢指针都进入环后，最终会相遇。

扩展：

为什么慢指针一次走一步，快指针一次走两步，在带环链表中会出现相遇情况？

假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在慢指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。

快指针一次走三步，四步……，还能不能相遇？

不一定能相遇

9.3 AC代码

bool hasCycle(struct ListNode *head) {
    struct ListNode* fast = head, *slow = head;
    while(fast && fast->next)//slow和fast都进入环后，追及问题
    {
        slow = slow->next;
        fast = fast->next->next;

        if(slow == fast)
            return true;
    }

    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

10. 环形链表 II

LeetCode链接：环形链表 II

10.1 题目描述

要求：判断相交，再找环入口点

10.2 解决思路

思路一：数学问题

思路二：我们把meet断开，转换成相交链表求第一个交点的问题，但写起来比思路一复杂点，从这里也可看出，带环问题和相交问题可互相转换，这里就不给实现代码了。

10.3 AC代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* slow,*fast;
    slow = fast = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;

        if(slow == fast)
        {
            struct ListNode* meet = slow;
            while(meet != head)
            {
                meet = meet->next;
                head = head->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
30

11. 复制带随机指针的链表

LeetCode链接：复制带随机指针的链表

11.1 题目描述

要求：给定一个链表，每个结点包含一个额外增加的随机指针，该指针可以指向链表中的任何结点或空结点。要拷贝出一个同样的新链表。

11.2 解决思路

11 .3 AC代码

/**
 * 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* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;

        copy->next = cur->next;
        cur->next = copy;

        cur = copy->next;
    }
    
    //2.
    cur = head;
    while(cur)
    {
        struct Node* copy = cur->next;
        if(cur->random == NULL)
        {
            copy->random = NULL;
        }
        else
        {
            copy->random = cur->random->next;
        }

        cur = copy->next;
    }

    //3.尾插
    cur = head;
    struct Node* copyHead = NULL,*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
64

学习记录：

本篇博客整理于2022.6.23~2022.7.3
如果有错误的地方请多多指教🌹🌹🌹

相关阅读:
Sentinel的简单介绍和使用
 零基础入门JavaWeb——JS的事件驱动
 设计模式之享元模式
 使用kubekey的all-in-one安装K8S1.24及KubeSphere3.3
免费、好用、强大的 Markdown 编辑器综合评测和推荐
 Python期末复习题：函数
 Biotin-LC（CAS:72040-64-3）含有的 NHS 酯起到哪些化学效应了？
Feign实现动态URL
SpringBoot中required a bean of type ‘java.lang.String‘ that could not be found问题
 20天深度复习JavaSE的详细笔记(十二)——集合（Collection、数据结构、List、泛型深入）
原文地址：https://blog.csdn.net/m0_62080641/article/details/125513211

单链表相关OJ题（LeetCode、C语言、数据结构）

文章目录

1. 移除链表元素

1.1 题目描述

1.2 解决思路

1.3 AC代码

2. 反转链表

2.1 题目描述

2.2 解决思路

2.3 AC代码

3. 链表的中间结点

3.1 题目描述

3.2 解决思路

3.3 AC代码

4. 链表中倒数第k个结点

4.1 题目描述

4.2 解决思路

4.3 AC代码

5. 合并两个有序链表

5.1 题目描述

5.2 解决思路

5.3 AC代码

6. 链表分割

6.1 题目描述

6.2 解决思路

6.3 AC代码

7. 链表的回文结构

7.1 题目描述

7.2 解决思路

7.3 AC代码

8. 相交链表

8.1 题目描述

8.2 解决思路

8.3 AC代码

9. 环形链表

9.1 题目描述

9.2 解决思路

9.3 AC代码

10. 环形链表 II

10.1 题目描述

10.2 解决思路

10.3 AC代码

11. 复制带随机指针的链表

11.1 题目描述

11.2 解决思路

11 .3 AC代码