链表

基础函数与节点定义

点我查看 
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
#define INF 0x3f3f3f3f
struct ListNode{
	int val;
	ListNode* next;
	ListNode(int x, ListNode* nextListNode): val(x), next(nextListNode) {}
	ListNode(int x):val(x), next(nullptr) {}
};
/**
 * @brief 打印单链表
 * 
 * @param root 单链表
 */
void dispWithoutHeadNodeList(ListNode* root){
	ListNode* p=root;
	while(p){
		cout<<p->val<<" ";
		p=p->next;
	}
	cout<<endl;
	p=nullptr;
}
/**
 * @brief 打印带头结点单链表
 * 
 * @param root 带头结点单链表
 */
void dispWithHeadNodeList(ListNode* root){
	ListNode* p=root;
	while(p->next){
		cout<<p->next->val<<" ";
		p=p->next;
	}
	cout<<endl;
	p=nullptr;
}

习题代码

点我查看

综合应用第一题

点我查看 
1
2
3
4
5
6
ListNode* removeNode(ListNode* root, int x){
	if(root==nullptr)return nullptr;
	if(root->val == x)return removeNode(root->next, x);
	root->next=removeNode(root->next, x);
	return root;
}

image-20230509213007407

image-20230509213032640

综合应用题第二题

点我查看 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
ListNode* removeNodeWithoutHeadNode(ListNode* root, int x){
	if(root==nullptr)return nullptr;
	if(root->val == x)return removeNodeWithoutHeadNode(root->next, x);
	root->next=removeNodeWithoutHeadNode(root->next, x);
	return root;
}
ListNode* removeNodeWithHeadNode(ListNode* root, int x){
	ListNode* p=root;
	ListNode* t=nullptr;
	while(p->next){
		if(p->next->val==x){
			t=p->next;
			p->next=p->next->next;
			delete t;
		}else{
			p=p->next;
		}
	}
	return root;
}

image-20230509214728513

综合应用题第三题

点我查看 
1
2
3
4
5
6
7
8
void reverseDispWithoutHeadNodeList(ListNode* root){
	if(!root)return;
	reverseDispWithoutHeadNodeList(root->next);
	cout<<root->val<<" ";
}
void reverseDispWithHeadNodeList(ListNode* root){
	reverseDispWithoutHeadNodeList(root->next);
}

image-20230509220852809

综合应用题第四题

点我查看 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ListNode* removeMinElementNode(ListNode* root){
	if(!root->next)return root;
	ListNode* p=root;
	ListNode* t=root;
	while(p->next){
		if(p->next->val < t->next->val){
			t=p;
		}
		p=p->next;
	}
	p=t->next;
	t->next=t->next->next;
	delete p;
	return root;
}

综合应用题第五题

点我查看 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @brief 空间复杂度O(1)的逆序链表算法
 * 
 * @param root 原始链表（带头结点）
 * 
 * @return 逆序后的链表
 */
ListNode* Space_O1_reverse(ListNode* root){
	ListNode* beginNode = root->next;
	if(!beginNode)return root;
	ListNode* endNode = beginNode->next;
	while(endNode){
		beginNode->next=endNode->next;
		endNode->next=root->next;
		root->next=endNode;
		endNode=beginNode->next;
	}
	return root;
}

综合应用题第六题

点我查看 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @brief 排序带头结点的链表
 * 
 * @param root 待排序的链表
 * 
 * @return 排序后的链表
 */
ListNode* sortList(ListNode* root){
	vector<int> element;
	ListNode* p=root;
	while(p->next){
		element.push_back(p->next->val);
		p=p->next;
	}
	sort(element.begin(), element.end());
	p=root;
	for(auto i:element){
		p->next->val=i;
		p=p->next;
	}
	return root;
}

image-20230509223857603

综合应用题第七题

点我查看 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @brief 删除 l<=val<=r 的子节点
 * 
 * @param l 左值
 * @param r 右值
 * @param root 带头结点的原始链表
 * 
 * @return 删除后的带头结点的链表
 */
ListNode* deleteIntervalElement(ListNode* root,int l, int r){
	ListNode* p=root;
	ListNode* t=nullptr;
	while(p->next){
		if(p->next->val >= l && p->next->val <= r){
			t = p->next;
			p->next = p->next->next;
			delete t;
		}else{
			p = p->next;
		}
	}
	return root;
}

image-20230510224115752

综合应用题第八题

点我查看 
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
/**
 * @brief 寻找两个带头结点的链表的第一个公共子节点
 * 
 * @param headA 带头结点的链表1
 * @param headB 带头结点的链表2
 * 
 * @return 第一个公共子节点
 */
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB){
	ListNode *p=headA, *t=headB;
	int l1=0, l2=0;
	while(p->next){
		p=p->next;
		l1++;
	}
	while(t->next){
		t=t->next;
		l2++;
	}
	p=headA;
	t=headB;
	if(l1!=l2){
		if(l1>l2){
			while(l1-l2){
				p=p->next;
				l1--;
			}
		}else{
			while(l2-l1){
				t=t->next;
				l2--;
			}
		}
	}
	while(p->next){
		if(p->next == t->next){
			return p->next;
		}
		p=p->next;
		t=t->next;
	}
	return nullptr;
}

image-20230513190548671

综合应用题第九题

点我查看 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @brief 递增次序输出并删除节点
 * 
 * @param root 带头结点的原始链表
 */
void incrementOutputAndFree(ListNode* root){
	ListNode* p=root;
	ListNode* t=nullptr, *tt=nullptr;
	while(p->next){
		t=p;
		tt=p;
		while(tt->next){
			if(tt->next->val > t->next->val){
				t=tt;
			}
			tt=tt->next;
		}
		tt=t->next;
		t->next = tt->next;
		cout<<tt->val<<" ";
		delete tt;
	}
}

image-20230513191847509

综合应用题第十题

点我查看 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @brief 分解链表
 * 
 * @param headA 原始头结点，运行函数后变为存储奇数序号子节点的头结点
 * @param headB 存储偶数序号子节点的头结点
 */
void decomposeListNode(ListNode* headA, ListNode* headB){
	ListNode *p=headA, *t=headB;
	while(p && p->next){
		t->next = p->next->next;
		t=t->next;
		p->next->next = t->next;
		t->next = nullptr;
		p = p->next;
	}
}

image-20230513194946323

综合应用题第十一题

点我查看 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @brief 分解链表
 * 
 * @param headA 原始头结点，运行函数后变为存储奇数序号子节点的头结点
 * @param headB 存储偶数序号子节点的头结点并逆序
 */
void decomposeListNode(ListNode* headA, ListNode* headB){
	ListNode *p=headA, *t=headB;
	while(p && p->next){
		t->next = p->next->next;
		t=t->next;
		p->next->next = t->next;
		t->next = nullptr;
		p = p->next;
	}
    Space_O1_reverse(headB); // 逆序headB, 空间复杂度O(1),综合应用第五题答案
}

image-20230513200250925

综合应用题第十二题

点我查看 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @brief 去重链表元素
 * 
 * @param head 待去重的链表（带头结点）
 */
void deduplicationListNode(ListNode* head){
	ListNode* p=head->next, *t=nullptr;
	while(p && p->next){
		if(p->next->val == p->val){
			t=p->next;
			p->next = t->next;
			delete t;
		}else p=p->next;
	}
}

image-20230513201047896

综合应用题第十三题

点我查看 
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
/**
 * @brief 合并两个递增单链表并逆序
 * 
 * @param list1 链表1
 * @param list2 链表2
 * 
 * @return 合并后逆序的单链表
 */
ListNode* mergeList(ListNode* list1, ListNode* list2){
	ListNode *head = new ListNode(-INF);
	ListNode *p=head, *t=list1, *q=list2;
	while(t && q){
		if(t->val < q->val){
			p->next = t;
			t = t->next;
		}else{
			p->next = q;
			q = q->next;
		}
		p = p->next;
	}
	if(t){
		p->next = t;
	}else{
		p->next = q;
	}
	head = Space_O1_reverse(head);
	return head->next;
}

image-20230517114105570

综合应用题第十四题

点我查看 
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
/**
 * @brief 寻找两个单链表的公共元素（不破坏两个链表）
 *
 * @param headA 单链表1
 * @param headB 单链表2
 * @return 
 */
ListNode* findCommonElements(ListNode* headA, ListNode* headB) {
	ListNode *p = headA, *t = headB;
	ListNode *reList = nullptr, *q = nullptr;
	while(p->next && t->next){
		if(p->next->val == t->next->val){
			if(!q){
				reList = new ListNode(p->next->val);
				q = reList;
			}else{
				q->next = new ListNode(p->next->val);
				q = q->next;
			}
			p = p->next;
			t = t->next;
		}else if(p->next->val < t->next->val){
			p = p->next;
		}else{
			t = t->next;
		}
	}
	return reList;
}

image-20230517115747182

综合应用题第十五题

点我查看 
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
/**
 * @brief 寻找两个单链表的公共元素（存在链表1中）
 *
 * @param headA 单链表1
 * @param headB 单链表2
 * @return 
 */
void findCommonElements(ListNode* headA, ListNode* headB) {
	ListNode *p = headA, *t = headB, *q = nullptr;
	while(p->next && t->next){
		if(p->next->val == t->next->val){
			p = p->next;
			t = t->next;
		}else if(p->next->val < t->next->val){
			q = p->next;
			p = p->next->next;
			delete q;
		}else{
			t = t->next;
		}
	}
	t = headB;
	while(t->next){
		q = t->next;
		t = t->next->next;
		delete q;
	}
}

image-20230517120615148

综合应用题第十六题

点我查看 
          </div>        </details>