OJ ：反转链表、移除单链表的元素、合并两个有序链表、链表分割 |【哨兵位】| C_哨兵位方便头插还是尾插

必备知识：单链表的增删查改

【数据结构初阶】-3-链表 | 链表是什么？| 【单链表的增删查改|思路+源码】

概览及题目链接

• 一、反转链表（头插）leetcode题目链接

• 二、移除单链表的元素（尾插）leetcode题目链接

• 三、合并两个有序链表（尾插）leetcode题目链接
  

• 四、链表分割（尾插）牛客网题目链接

题一：反转链表（头插）

思路一：依次反转

源码

注意：不能对空指针解引用！
易错：

struct ListNode* n3 = head->next;  //如果head不能NULL（所以要提前处理head为NULL的情况）

if (n3)
{
	n3 = n3->next; //最后一次循环中n3已经为NULL不能对其解引用
	//（所以对n3是否为空要进行判断！）
}
1
2
3
4
5
6
7

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

思路二：依次头插

源码

struct ListNode* reverseList1(struct ListNode* head)
{
	if (head == NULL)
	{
		return NULL;
	}
	struct ListNode* cur = head;
	struct ListNode* next = head->next;
	struct ListNode* newhead = NULL;
	while (cur)
	{
		cur->next = newhead;
		newhead = cur;
		cur = next;
		if (next)
			next = next->next;
	}
	return newhead;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

（本质上以上两个代码的实现没有很大的区别，思路一更像是思路二的具体化）

题二：移除单链表的元素（尾插）

思路：非val的尾插

• 首先，如上。移除链表元素后的链表的头节点可能被更改，因此我们要先解决头节点的问题。
  我们根据head寻找链表中第一个有效的头节点，它是第一个尾插的对象（虽然它实际上它并没有插入谁），此时，我们需要考虑，移除链表元素后的newhead是否为空？
• 移除链表元素后的head是否为空？
  • 链表本身为空链表（如上，示例2）
  • 因为非val的将被尾插，然而从第一个结点到最后一个结点我们未找到第一个（此时也是唯一一个）非val的结点（如上，示例3）

综上，尾插的时候有一次必要的判断（详情见完整源码）

if (!newhead)
{
	newhead = cur;
}
1
2
3
4

注意：但凡对指针进行了解引用的都有必要判断这个指针是否为空，不能对空指针解引用！

if (next)
	next = next->next;
if (tail)
	tail->next = NULL;
1
2
3
4

源码（无哨兵位头节点）

//无哨兵位
struct ListNode* removeElements1(struct ListNode* head, int val)
{
	if (!head)
		return NULL;
	struct ListNode* cur = head, * next = head->next;
	struct ListNode* newhead = NULL, * tail = NULL;
	//尾插
	while (cur)
	{
		if (cur->val == val)
		{
			free(cur);
			cur = next;
			if (next)
				next = next->next;
		}
		else
		{
			if (!newhead)
			{
				newhead = cur;
			}
			else
			{
				tail->next = cur;
			}
			tail = cur;
			cur = next;
			if (next)
				next = next->next;
		}
	}
	if (tail)
		tail->next = NULL;
	if (newhead)
		return newhead;
	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
31
32
33
34
35
36
37
38
39

【哨兵位头结点】

哨兵位头节点：不存储有效数据的头节点（malloc申请一块空间作为形式上的头节点）

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/凡人多烦事01/article/detail/585951