目录
NC25 删除有序链表中重复的元素-I
描述
方法一:遍历删除(推荐使用)
方法二:递归求解
反转链表
描述
解法:迭代
给大家推荐一款神器牛客网以下题型及方法牛客都有,及企业面试高频题
文章来源地址https://www.toymoban.com/news/detail-568883.html
NC25 删除有序链表中重复的元素-I
描述
删除给出链表中的重复元素(链表中元素从小到大有序),使链表中的所有元素都只出现一次
例如:
给出的链表为1→1→2,返回1→2.
给出的链表为1→1→2→3→3,返回1→2→3.
数据范围:链表长度满足0≤n≤100,链表中任意节点的值满足val∣≤100
进阶:空间复杂度 O(1)O(1),时间复杂度 O(n)O(n)
我们可以在题目得到这样的信息:
- 给定一个从小到大排好序的链表
- 删去链表中重复的元素,每个值只留下一个节点
方法一:遍历删除(推荐使用)
思路:
既然连续相同的元素只留下一个,我们留下哪一个最好呢?当然是遇到的第一个元素了!
if(cur->val==cut->next->val)
cur->var=cur->next->next;
因为第一个元素直接就与前面的链表节点连接好了,前面就不用管了,只需要跳过后面重复的元素,连接第一个不重复的元素就可以了,在链表中连接后面的元素总比连接前面的元素更方便嘛,因为不能逆序访问。
具体做法:
- step 1:判断链表是否为空链表,空链表不处理直接返回。
- step 2:使用一个指针遍历链表,如果指针当前节点与下一个节点的值相同,我们就跳过下一个节点,当前节点直接连接下个节点的后一位。
- step 3:如果当前节点与下一个节点值不同,继续往后遍历。
- step 4:循环过程中每次用到了两个节点值,要检查连续两个节点是否为空。
动图展示:
核心代码
struct ListNode* deleteDuplicates(struct ListNode* head ) {
if(head == NULL || head->next == NULL) return head;
struct ListNode *p=head,*pn = head->next;
while(p){
if(p->val == pn->val){
while(pn&&pn->val == p->val) //判断
pn = pn->next;
p->next = pn;//删除
}
p = p->next;
}
return head;
// write code here
}
复杂度分析:
- 时间复杂度:O(n)O(n)O(n),其中nnn为链表长度,遍历一次链表
- 空间复杂度:O(1)O(1)O(1),常数级指针变量使用,没有使用额外的辅助空间
方法二:递归求解
核心思想:
采用递归的思想求解。每次递归则需要比较并删除重复的元素。本次的思想跟递归逆置链表很像,唯一的不同就是处理逻辑不同。删除重复链表的处理逻辑是每次都要删除当前节点(如果当前节点与下一个节点相同时候)
核心代码:
ListNode* deleteDuplicates(ListNode* head) {
if (head == nullptr || head->next == nullptr) //节点不存在或者只有一个节点时,递归结束
return head;
head->next = deleteDuplicates(head->next); //递归体,每次递归从下一个节点开始
if (head->val == head->next->val) //比较当前元素和下一个元素的值是否相等,相等则直接删除当前节点
head = head->next; //head指针指向下一个节点,表明当前节点丢失,已经不再属于这个链表
return head; //返回本次递归的结果
}
复杂度分析:
递归n次,因此时间复杂度为O(N)。而每次递归都需要一个额外的变量保存,因此空间复杂度为O(N),时间复杂度O(n)
反转链表
描述
给定一个单链表的头结点pHead(该头节点是有值的,比如在下图,它的val是1),长度为n,反转该链表后,返回新链表的表头。
数据范围:0≤n≤1000
要求:空间复杂度 O(1)O(1) ,时间复杂度 O(n)O(n) 。
如当输入链表{1,2,3}时,
经反转后,原链表变为{3,2,1},所以对应的输出为{3,2,1}。
以上转换过程如下图所示:
解法:迭代
- 在遍历链表时,将当前节点的next 指针改为指向前一个节点。由于节点没有引用其前一个节点,因此必须事先存储其前一个节点。在更改引用之前,还需要存储后一个节点。最后返回新的头引用。
- 图解:
复杂度分析:
时间复杂度:O(N),其中 N 是链表的长度。需要遍历链表一次。
空间复杂度:O(1),常数空间复杂度
代码展示:
```/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*
* C语言声明定义全局变量请加上static,防止重复定义
*/
struct ListNode* ReverseList(struct ListNode* pHead ) {
if(!pHead)return NULL;
if(pHead->next==NULL)return pHead;
struct ListNode *p,*t;
t=pHead->next;
p=pHead;p->next=NULL;
while(t){
p=t;
t=t->next;
p->next=pHead;
pHead=p;
}
return p;
}
点击右边链接牛客网 - 找工作神器|笔试题库|面试经验|实习招聘内推,求职就业一站解决_牛客网
文章来源:https://www.toymoban.com/news/detail-568883.html
到了这里,关于[C语言刷题篇]链表运用讲解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!