链表专项练习(二)
一、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还小 ，所以再次头插
三、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.断开原节点与拷贝节点的联系 并返回拷贝节点 例：