上一篇文章带大家详细的学习了单链表的基本操作,例如创建单链表,单链表的头插尾插,头删尾删等等。这篇博客就带大家手撕几道链表有关经典高频OJ题目。来供大家更加深刻地理解链表的知识。
第一题:合并两个有序链表
OJ链接:21. 合并两个有序链表 - 力扣(LeetCode)
首先,两个链表是有序的,且都是升序的,这就启发我们将两个链表同时遍历。思路如下:
一 . 创建一个新链表,来存放合并后的链表。
二 . 两个链表同时遍历,数据小的节点尾插到新链表当中。
三 . 一定会有一个链表先遍历完毕。当一个链表先遍历完毕,还没遍历完的那个链表节点的数据一定大于新链表中的数据,且是升序,可以直接将没遍历完的那个链表尾插到新链表。
有了以上思路,接下来就是具体的代码实现 以及 代码的细节处理。实现代码如下:
1. /** 2. * Definition for singly-linked list. 3. * struct ListNode { 4. * int val; 5. * struct ListNode *next; 6. * }; 7. */ 8. struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 9. { 10. struct ListNode* cur1=list1;//备份list1的头节点,用来遍历 11. struct ListNode* cur2=list2;//备份list2的头节点,用来遍历 12. struct ListNode* newhead=NULL;//新链表,用来尾插两个链表较小的节点 13. struct ListNode* tail=NULL;//用来代表尾插时的尾节点,不断更新就可以代表新链表的尾节点 14. while(cur1&&cur2)//两个链表都没遍历完就继续同时遍历 15. { 16. if(cur1->val<=cur2->val)//比较数据大小,决定尾插cur1还是cur2 17. { 18. //尾插cur1 19. if(newhead==NULL)//尾插的细节,空链表尾插需要按照头插的逻辑 20. { 21. //头插cur1 22. newhead=cur1; 23. tail=newhead;//更新tail 24. } 25. else//新链表不为空,在tail后面插入 26. { 27. tail->next=cur1;//链接cur1 28. tail=tail->next;//更新tail 29. } 30. cur1=cur1->next;//需要遍历list1,cur1向后迭代 31. } 32. else 33. { 34. //尾插cur2 35. if(newhead==NULL)//尾插的细节,空链表尾插需要按照头插的逻辑 36. { 37. //头插cur2 38. newhead=cur2; 39. tail=newhead;//更新tail 40. } 41. else 42. { 43. tail->next=cur2;//链接cur2 44. tail=tail->next;//更新tail 45. } 46. cur2=cur2->next;//需要遍历list2,cur2向后迭代 47. } 48. } 49. //到这里·有一个链表就遍历完了,此时可能还剩一个链表没遍历完 50. if(cur1)//cur1不为空,还没遍历完 51. { 52. if(tail==NULL)//应对极端情况,cur2天生就是空,导致新链表还没开始尾插,tail还是空 53. { 54. newhead=cur1; 55. } 56. else//如果tail还是NULL会有空指针解引用错误,所以上面先判断一下 57. tail->next=cur1; 58. } 59. else if(cur2)//cur2不为空,还没遍历完 60. { 61. if(tail==NULL)//应对极端情况,cur1天生就是空,导致新链表还没开始尾插,tail还是空 62. { 63. newhead=cur2; 64. } 65. else//如果tail还是NULL会有空指针解引用错误,所以上面先判断一下 66. tail->next=cur2; 67. } 68. return newhead;//返回新链表 69. }
在写OJ题时,以下两点非常重要。
一 . 分析思路,画图。
二 . 记得分析极端场景,持着先普通再极端的道理。