链表学会了没，会做这些题就足够了，思路全在动图里了，不懂都难

发表于

小知识，大挑战！本文正在参与「程序员必备小知识」创作活动

本文已参与 「掘力星计划」 ，赢取创作大礼包，挑战创作激励金。

1.移除链表元素 ＜难度系数⭐＞

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

💨 示例1：

    输入：head = [1,2,6,3,4,5,6], val = 6

    输出：[1,2,3,4,5]

💨 示例2：

    输入：head = [ ], val = 1

    输出：[ ]

💨 示例3：

    输入：head = [7,7,7,7], val = 7

    输出：[ ]

在这里插入图片描述

🧷 平台：Visual studio 2017 && windows

🔑 核心思想：

思路1，双指针，cur找到val值所在的节点，prev记录前一个位置，依次删除，细节请看下图：

请添加图片描述

思路2，新链表，把链表中所有不是val的值尾插至新链表，删除val的节点

请添加图片描述

leetcode原题

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
c复制代码#include<stdio.h>
#include<stdlib.h>

typedef int SLTDataType;

struct ListNode
{
	int val;
	struct ListNode *next;
};
//思路1
struct ListNode* removeElements1(struct ListNode* head, int val)
{
	struct ListNode * cur = head;
	struct ListNode * prev = NULL;
	while (cur)//判断地址
	{
		//1、相等的情况
		if (cur->val == val)
		{
			if (cur == head)//1.1、第1个节点等于val时
			{
				head = head->next;
				free(cur);
				cur = head;
			}
			else//1.2、其它节点等于val时
			{
				prev->next = cur->next;
				free(cur);
				cur = prev->next;
			}
		}
		//2、不相等的情况
		else
		{
			prev = cur;
			cur = cur->next;
		}
	}
	return head;

}
//思路2
struct ListNode* removeElements2(struct ListNode* head, int val)
{	
	if(head == NULL)
		return NULL;
	//创建新节点
	struct ListNode* newhead = NULL, *tail = NULL;
	struct ListNode* cur = head;
	while(cur)
	{
		struct ListNode* next = cur->next;
		if(cur->val == val)
		{
			free(cur);
		}
		else
		{
			if(tail == NULL)
			{
				newhead = tail = cur;	
			}
			else
			{
				tail->next = cur;	
				tail = cur;
			}
		}
		cur = next;
	}
	if(tail)
		tail->next = NULL;
	return newhead;
}
int main()
{
	struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n1->val = 1;

	struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n2->val = 2;

	struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n3->val = 6;

	struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n4->val = 3;

	struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n5->val = 4;

	struct ListNode* n6 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n6->val = 5;

	struct ListNode* n7 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n7->val = 6;

	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = n5;
	n5->next = n6;
	n6->next = n7;
	n7->next = NULL;

	removeElements1(n1, 6);
	removeElements2(n1, 6);
	return 0;
}

2.反转一个链表＜难度系数⭐＞

📝 题述：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

💨 示例1：

    输入：head = [1,2,3,4,5]

    输出：[5,4,3,2,1]

💨 示例2：

    输入：head = [1,2]

    输出：[2,1]

💨 示例3：

    输入：head = [ ]

    输出：[ ]

在这里插入图片描述

🧷 平台：Visual studio 2017 && windows

🔑 核心思想：

思路1，调整节点指针的方向
请添加图片描述

思路2，头插

请添加图片描述

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
c复制代码#include<stdio.h>
#include<stdlib.h>

typedef int SLTDataType;

struct ListNode
{
	int val;
	struct ListNode *next;
};
//思路1
struct ListNode* reverseList1(struct ListNode* head)
{
	//空链表
    if(head == NULL)
        return head;
    struct ListNode* n1, *n2, *n3;
    n1 = NULL;
    n2 = head;
    n3 = head->next;

    while(n2)
    {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        //最后一次进来时，n3为空指针
        if(n3)
            n3 = n3->next;
    }
    return n1;
}
//思路2
struct ListNode* reverseList2(struct ListNode* head)
{
	struct ListNode *newnode, *cur, *next;
    newnode = NULL;
    cur = head;
    while(cur)
    {
        next = cur->next;   
        cur->next = newnode;
        newnode = cur;
        cur = next;
    }
    return newnode;
}
int main()
{
	struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n1->val = 1;

	struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n2->val = 2;

	struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n3->val = 3;

	struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n4->val = 4;

	struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n5->val = 5;
	
	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = n5;
	n5->next = NULL;
	
	reverseList1(n1);
	reverseList2(n1);
	return 0;
}

3.链表的中间结点＜难度系数⭐＞

📝 题述：给定一个头结点为 head 的非空单链表，返回链表的中间结点。 如果有两个中间结点，则返回第二个中间结点。

在这里插入图片描述

💨 示例1：

    输入：[1,2,3,4,5]

    输出：此列表中的结点 3 (序列化形式：[3,4,5])返回的结点值为 3 。 (测评系统对该结点序列化表述是 ([3,4,5])。注意，我们返回了一个 ListNode 类型的对象 ans，这样：ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

🧷 平台：Visual studio 2017 && windows

🔑 核心思想：

快慢指针，快指针走2步，慢指针走1步，当快指针走完后，慢指针的当前位置就是中间节点

请添加图片描述

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
c复制代码#include<stdio.h>
#include<stdlib.h>

typedef int SLTDataType;

struct ListNode
{
	int val;
	struct ListNode *next;
};
struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode *slow, *fast;
    slow = fast = head;
    //必须同时满足奇偶的条件
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
int main()
{
	struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n1->val = 1;

	struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n2->val = 2;

	struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n3->val = 3;

	struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n4->val = 4;

	struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n5->val = 5;
	
	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = n5;
	n5->next = NULL;

	middleNode(n1);
	return 0;
}

4.链表中倒数第k个节点＜难度系数⭐＞

📝 题述：输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

💨 示例：

    给定一个链表: 1->2->3->4->5, 和 k = 2.

    返回链表 4->5

在这里插入图片描述

🧷 平台：Visual studio 2017 && windows

🔑 核心思想：

快慢指针，快指针先走k步，此时它与慢指针相差的就是k步，然后快慢指针同时1步1步的走，直到快指针指向NULL，此时慢指针指向的节点就是目标节点

请添加图片描述

leetcode原题

牛客网原题

⚠ 这道题我在两个平台都做了下，按照常规的写法，发现它在leetcode能过的代码，在牛客网上却过不了

请添加图片描述

所以我们这里使用更严格的写法

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
c复制代码#include<stdio.h>
#include<stdlib.h>

typedef int SLTDataType;

struct ListNode
{
	int val;
	struct ListNode *next;
};
struct ListNode* getKthFromEnd(struct ListNode* head, int k)
{
	if(k == 0)
        return NULL;
	struct ListNode *slow, *fast;
    slow = fast = head;
    //fast先走k步
    while(k--)
    {
		//如果k大于链表的长度
        if(fast == NULL)
            return NULL;    
        fast = fast->next;
    }
    //slow和fast同时走，直至fast指向空
    while(fast)
    {
        slow = slow->next;
        fast = fast->next;
    }
    
    return slow;
}
int main()
{
	struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n1->val = 1;

	struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n2->val = 2;

	struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n3->val = 3;

	struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n4->val = 4;

	struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n5->val = 5;
	
	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = n5;
	n5->next = NULL;

	getKthFromEnd(n1, 2);
	return 0;
}

5.合并两个有序链表＜难度系数⭐＞

📝 题述：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

💨 示例1：

    输入：l1 = [1,2,4], l2 = [1,3,4]

    输出：[1,1,2,3,4,4]

💨 示例2：

    输入：l1 = [], l2 = []

    输出：[ ]

💨 示例3：

    输入：l1 = [ ], l2 = [0]

    输出：[0]

在这里插入图片描述

🧷 平台：Visual studio 2017 && windows

🔑 核心思想：

思路1，见下图

请添加图片描述

思路2，带哨兵位的头节点

请添加图片描述

在之前的文章中没有了解过什么是哨兵位头节点，在这里就了解下：

在这里插入图片描述

1️⃣ 哨兵位头节点，这个节点不存储有效数据；而非哨兵位头节点存储有效数据

2️⃣ 非哨兵位头节点如果要修改头指针，需要使用二级指针操作；而哨兵位头节点，则不会修改头指针，因为它不存储有效数据

3️⃣ 这种哨兵位头节点在实际中很少出现，包括哈希桶、临接表做子结构都是不带头的。其次就是OJ中给的链表都是不带头的(从上面做的这些题就可以看出)，所以我们在以后编码过程中，应该尽量使用不带头的

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
129
c复制代码#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>

typedef int SLTDataType;

struct ListNode
{
	int val;
	struct ListNode *next;
};
//思路1
struct ListNode* mergeTwoLists1(struct ListNode* l1, struct ListNode* l2)
{
	struct ListNode *n1 = l1, *m1 = l2;
	struct ListNode *newhead = NULL, *tail = NULL;
	//判断空链表
    if(l1 == NULL)
        return l2;
    if(l2 == NULL)
        return l1;
        
	while(n1 && m1)
	{
		if(n1->val < m1->val)
		{
			if(newhead == NULL)
			{
				newhead = tail = n1;
			}
			else
			{
				tail->next = n1;
				tail = n1;
			}	
			n1 = n1->next;		
		} 
		else
		{
			if(newhead == NULL)
			{
				newhead = tail = m1;
			}
			else
			{
				tail->next = m1;
				tail = m1;
			}
			m1 = m1->next;
		}
	}
	//链接上剩余的数据
    if(n1)
        tail->next = n1;
    if(m1)
        tail->next = m1;
        
    return newhead;
}
//思路2
struct ListNode* mergeTwoLists2(struct ListNode* l1, struct ListNode* l2)
{
	struct ListNode *n1 = l1, *m1 = l2;
	struct ListNode *newhead = NULL, *tail = NULL;
    //判断空链表
    if(l1 == NULL)
        return l2;
    if(l2 == NULL)
        return l1;
    //申请空间
    newhead = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
	while(n1 && m1)
	{
		if(n1->val < m1->val)
		{
			tail->next = n1;
			tail = n1;	
			n1 = n1->next;		
		} 
		else
		{
			tail->next = m1;
			tail = m1;
			m1 = m1->next;
		}
	}
    //链接上剩余的数据
    if(n1)
        tail->next = n1;
    if(m1)
        tail->next = m1;
    //这里返回的是不带哨兵位的头节点。其次malloc开辟了空间，就要主动释放，否则会内存泄漏
    struct ListNode* first = newhead->next;
    free(newhead);
    return first;
}
int main()
{
	struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n1->val = 1;

	struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n2->val = 2;

	struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n3->val = 4;

	n1->next = n2;
	n2->next = n3;
	n3->next = NULL;
	/*----------------------------------分割------------------------------------*/
	struct ListNode* m1 = (struct ListNode*)malloc(sizeof(struct ListNode));
	m1->val = 1;

	struct ListNode* m2 = (struct ListNode*)malloc(sizeof(struct ListNode));
	m2->val = 3;

	struct ListNode* m3 = (struct ListNode*)malloc(sizeof(struct ListNode));
	m3->val = 4;

	n1->next = n2;
	n2->next = n3;
	n3->next = NULL;
	
	mergeTwoLists1(n1, m1);
	mergeTwoLists2(n1, m1);
	
	return 0;
}

请添加图片描述

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%