数据结构——链表OJ题

数据结构——链表OJ题,第1张

目录

 

1.给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。

2.给定一个带有头结点 head 的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。

3.变形题:找到链表中倒数第k个节点

4.经典题:将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

结语


个人主页:大耳朵土土垚-CSDN博客

所属专栏:数据结构学习笔记

 

数据结构——链表OJ题,46ea021929244f569b734890b6cd428a.jpeg,第2张

1.给你一个链表的头节点 

head

 和一个整数 

val

 ,请你删除链表中所有满足 

Node.val == val

 的节点,并返回 新的头节点 。

示例 1:

 

数据结构——链表OJ题,df2d7ecde8b848737a0ca6ac7c9a636f.jpeg,第3张

输入:head = [1,2,6,3,4,5,6], val = 6
输出:[1,2,3,4,5]

解题思路:

创建指针遍历链表找到对应节点删除;

创建两个指针变量cur和pre用来记录,cur表示当前遍历的节点,pre表示上一个节点如图所示

数据结构——链表OJ题,3ff9993adfbe4e01b999e8896e3cfead.jpeg,第4张

不要忘了有两种情况,当第一个节点就是对应节点时需要将头指针head改变 ;

如果忘记第一种情况就会发现以下示例:

数据结构——链表OJ题,c99019dab9c3478ba86c08c1c69e7e20.png,第5张

图中null就是指pre为空指针的情况;

以下是完整代码实现: 

struct ListNode { int val; struct ListNode* next; }; struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode* cur = head; struct ListNode* pre = NULL; while (cur) { if (cur->val == val)//找到val值相同的节点时 { if (pre == NULL)//如果是第一个节点,也就是图中第②种 { cur = head->next; free(head); head = cur; } else//其他情况 { pre->next = cur->next; free(cur); cur = pre->next; } } else//不相同时 { pre = cur; cur = cur->next; } } return head; }

另外一种思路:

遍历链表,把不是val节点拿出来尾插,这里就不细讲有兴趣的可以打在评论区或私信我哦~

代码如下:

struct ListNode { int val; struct ListNode* next; }; struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode* cur = head; struct ListNode* newhead = NULL; struct ListNode* tail = NULL; while (cur) { if (cur->val != val) { if (newhead == NULL) { tail = cur; newhead = cur; } else { tail->next = cur; tail = tail->next; } cur = cur->next; tail->next = NULL; } else { struct ListNode* pos = cur; cur = cur->next; free(pos); } } return newhead; }

 

2.给定一个带有头结点 head 的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。

数据结构——链表OJ题,9775a355d8e643a4a7f4a67e6cfa45c9.png,第6张

解题思路:

给fast,slow两个指针,fast走两步,slow走一步 ,当fast走到尾时,slow恰好走到中间。

struct ListNode* middleNode(struct ListNode* head) { struct ListNode* fast = head, *slow = head; while(fast!=NULL&&fast->next != NULL) { slow = slow->next; fast = fast->next->next; } return slow; }

 

3.变形题:找到链表中倒数第k个节点

解题思路:

还是快慢指针,只要fast与slow之间距离为k,那么当fast走到终点时,slow所在的节点就是倒数第k个节点

数据结构——链表OJ题,a95ccf2e02f7435f98a87be76bfadc3a.png,第7张

 

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { // write code here struct ListNode* fast = pListHead,*slow = pListHead; for(int i = 0; i < k; i++)//先让fast走k步 { if(fast == NULL)//如果k大于链表长度记得要及时返回哦 return NULL; fast = fast->next; } while(fast) { fast = fast->next; slow = slow->next; } return slow; }

先让fast走k步拉开距离,然后fast与slow一起走,当fast为空指针时,slow即为倒数第k个节点;

 

 

4.经典题:将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

数据结构——链表OJ题,763a016ac41a448d98cb2ddc9ac61ccd.png,第8张

解题思路:

    取小的尾插

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { struct ListNode* head = NULL,*tail = NULL; if(list1 == NULL)//注意有链表为空的情况,直接返回另一个链表 return list2; if(list2 == NULL) return list1; while(list1 && list2)//注意这里是一个链表结束就都结束,所以两个都要为真用&& { if(list1->val <= list2->val) { if(head == NULL) { head = tail = list1; } else { tail->next = list1; tail = tail->next; } list1= list1->next; } else { if(head == NULL) { head = tail = list2; } else { tail->next = list2; tail = tail->next; } list2= list2->next; } } if(list1 == NULL) { tail->next = list2; } else { tail->next = list1; } return head; }

 要注意当有链表为空的情况,以及取小结束后的情况;

 

结语

链表尾插,我们可以用一个tail指针来记录尾插后的节点,尾插直接在tail节点后即可,这样就不用每次尾插都循环遍历,大大减少了时间复杂度 ,提高了运行效率。大家如果有什么问题或者想法欢迎打在评论区或私信我哦~

 

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/sjk/13518708.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2024-02-23
下一篇 2024-02-26

发表评论

登录后才能评论

评论列表(0条)

保存