一、JZ76 删除链表中重复的结点
描述
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表 1->2->3->3->4->4->5 处理后为 1->2->5
数据范围：链表长度满足 0 \le n \le 1000 \0≤n≤1000 ，链表中的值满足 1 \le val \le 1000 \1≤val≤1000
进阶：空间复杂度 O(n) ，时间复杂度 O(n)
在这里插入图片描述示例1输入：{1,2,3,3,4,4,5}返回值：{1,2,5}示例2输入：{1,1,1,8}返回值：{8}
/** * struct ListNode { * int val; * struct ListNode *next; * }; * * C语言声明定义全局变量请加上static，防止重复定义 */ /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param pHead ListNode类 * @return ListNode类 */ struct ListNode* deleteDuplication(struct ListNode* pHead ) { if(pHead==NULL||pHead->next==NULL) { return pHead; } struct ListNode*cur=pHead; struct ListNode*prev=NULL; struct ListNode*next=cur->next; while(next) { if(cur->val!=next->val) { prev=cur; cur=next; next=next->next; } else { while(next->val==cur->val&&next!=NULL) { next=next->next; } cur=next; if(prev!=NULL) { prev->next=next; } else { pHead=next; } if(next!=NULL) { next=next->next; } } } return pHead; }
本题需要考虑三种情况:
1.中间删除：
在这里插入图片描述
例：1 2 3 3 4 4 5
在这里插入图片描述
2.头删:
由于刚开始next值为NULL,所以直接将next赋给pHead
例：1 1 1 3 4
在这里插入图片描述
3.尾删:
next在循环中会一直走到NULL 所以要加上遍历条件
在这里插入图片描述
如果next为NULL ,NULL->next则会报错
在这里插入图片描述
例:2 3 4 5 5 5
在这里插入图片描述
二、147. 对链表进行插入排序
给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。
插入排序 算法的步骤:
插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。
下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。
对链表进行插入排序。
在这里插入图片描述
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* insertionSortList(struct ListNode* head){ if(head==NULL||head->next==NULL)//当为1个节点或2个节点 { return head; } struct ListNode*sorthead=head; struct ListNode*cur=head->next; sorthead->next=NULL; while(cur!=NULL) { struct ListNode*next=cur->next; if(cur->val<sorthead->val)//如果值比头节点小 就头插 { cur->next=sorthead; sorthead=cur; } else// 比头节点大 就中间插 /尾插 { struct ListNode*sortprev=sorthead; struct ListNode*sortcur=sorthead->next; while(sortcur!=NULL) { if(cur->val<=sortcur->val)//当在中间找到合适的插入点 { sortprev->next=cur; cur->next=sortcur; break;//找到后就跳出循环 } else { sortprev=sortcur; sortcur=sortcur->next; } } if(sortcur==NULL)//如果走到尾 说明要尾插 { sortprev->next=cur; cur->next=NULL; } } cur=next; } return sorthead; }
本题主要思想是， 将第一个节点单独拿出来，如果cur的值比它小，则进行头插，如果cur值比它大，
则进行 中间插或者尾插
例：
在这里插入图片描述1.
在这里插入图片描述因为2的值比sorthead小 所以头插 2.
在这里插入图片描述1比2还小 ，所以再次头插
3.
在这里插入图片描述
三、138. 复制带随机指针的链表
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。
在这里插入图片描述
/** * Definition for a Node. * struct Node { * int val; * struct Node *next; * struct Node *random; * }; */ struct Node* copyRandomList(struct Node* head) { struct Node*cur=head; if(head==NULL) { return NULL; } while(cur!=NULL)//1.拷贝节点到节点后面 { struct Node*copy=(struct Node*)malloc(sizeof(struct Node)); copy->next=NULL; copy->random=NULL; copy->val=cur->val; struct Node*next=cur->next; cur->next=copy; copy->next=next; cur=next; } cur=head; while(cur!=NULL)//2.原节点的random后一个是拷贝节点的random { struct Node*copy=cur->next; if(cur->random!=NULL) { copy->random=cur->random->next; } else { copy->random=NULL; } cur=copy->next; } cur=head; struct Node* copyhead=cur->next; while(cur!=NULL)//3.断开与拷贝节点连接 { struct Node*copy=cur->next; struct Node*next=copy->next; cur->next=next; if(next!=NULL) { copy->next=next->next; } else { copy->next=NULL; } cur=next; } return copyhead; }
本题主要思想为 1.拷贝出节点 并连接到原节点的后面 。2.通过原节点的random找到拷贝节点的random 。
3.断开原节点与拷贝节点的联系 并返回拷贝节点
例：
在这里插入图片描述
