单链表
链表的结点
typedef struct Node{
int data; //数据域
Node* next; //指针域,指向下一个结点
};
链表的打印
Notes:
- 链表的head不存储数据。
- 链表的最后一个元素的next指向NULL。
void PrintLinkList(Node* head){
Node* cur = head->next;
while(cur != NULL){
cout<<cur->data<<" ";
cur = cur->next;
}
cout<<endl;
}
链表的头插法
Notes:
- 链表的头会变成链表的尾,而链表的尾部都是指向NULL的,因此一上来就要把链表的head指向空。
- 头插法生成的链表的head->data是有数据的,因此可以生成一个new_head,使得new_head->head。这样就不会因为头结点的数据域有数据而感到尴尬。
Node* HeadInsert(Node* head,int arr[],int arrSize){
head = NULL; //Notes:1
for(int i = 0;i < arrSize;i++){
Node* new_node = new Node;
new_node->data = arr[i];
new_node->next = head; //Notes:1
head = new_node;
}
Node* new_head = new Node; //Notes:2
new_head->next = head;
return new_head;
}
链表的尾插法
Notes:
-
需要一个队尾指针rear记录队尾的位置,每次有新元素加入都必须更新rear。
-
每一个new_node->next都要指向NULL。
Node* RearInsert(Node head,int arr[],int arrSize){
Node* rear = head;
for(int i = 0;i < arrSize;i++){
Node* new_node = new Node;
new_node->data = arr[i];
new_node->next = NULL;
rear->next = new_node;
rear = rear->next;
}
return head;
}
链表的逆序(非递归)
Notes:
- 逆序前先判断链表的元素,不需要操作(head == NULL 或者 head->next == NULL)的话直接返回。
- 刚生成p1、p2、p3之后,p1将会是逆序之后的尾结点,所以需要p1->next = NULL。
- p1、p2、p3分别是head之后的第一、第二、第三个结点,整个链表逆序完之后头结点是不能有数据的,因此需要head->next = p2,这样就统一了。
Node* ReverseLinkList(Node* head){
if(head == NULL || head->next == NULL){
return head;
}
Node* p1 = head->next;
Node* p2 = p1->next;
Node* p3 = p2->next;
p1->next = NULL; //头变尾
while(p3 != NULL){
p2->next - p1;
p1 = p2;
p2 = p3;
p3 = p3->next;
}
p2->next = p1;
head->next = p2; //尾变头
return head;
}
链表的逆序(递归)
Notes:
- 用递归法返回的是pn->......->p2->p1->head->NULL。因此使用时千万注意方式
Node* ReverseLinkListRecursive(Node* head){
if(head == NULL || head->next == NULL){
return head;
}
Node* second = head->next;
Node* new_head = ReverseLinkListRecursive(second);
second->next = head;
head->next = NULL;
return new_head;
}
合并有序链表
Notes:
- 必须是两条排序方向相同的链表
- 如果一条链表为空,直接返回另一条链表即可
- 通常头结点都是不包含数据的,此时不需要事先确定头结点在哪条链表上。若头结点包含了数据,则需要确定新链表的头在哪条链表上。
- 一定要将新的链表头实例化,否则在确定哪个链表的结点是第一个元素时会出错(new_head->next = p1)。
- 用结点是否为空判断是否两条链表中都还存有元素,如果用结点的next指针判断会漏掉先循环完的那条链表的最后一个元素
- 若有一条链表先循环完,将指针指向另一个链表的剩下的第一个结点即可。
Node* MergeLinkList(Node* head1,Node* head2){
Node *p1,*p2,*pcur;
Node *new_head = new Node; //一定要开辟空间
if(head1->next == NULL){
return head2;
}
if(head2->next == NULL){
return head1;
}
if(head1->next == NULL && head2->next == NULL){
new_head = NULL;
return new_head;
}
//确定新链表的头结点
p1 = head1->next;
p2 = head2->next;
/*
if(p1->data <= p2->data){ //这一步是可以省的
new_head->next = p1;
p1 = p1->next;
}
else{
new_head->next = p2;
p2 = p2->next;
}
pcur = new_head->next;
*/
pcur = new_head;
while(p1 != NULL && p2 !=NULL){
if(p1->data <= p2->data){
pcur->next = p1;
pcur = pcur->next;
p1 = p1->next;
}
else{
pcur->next = p2;
pcur = pcur->next;
p2 = p2->next;
}
}
if(p1){
pcur->next = p1;
}
else{
pcur->next = p2;
}
return new_head;
}
原文链接: https://www.cnblogs.com/ziyuemeng/p/12370249.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/332331
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!