当前位置:   article > 正文

LeetCode --- 链表相关oj题 -- 1

LeetCode --- 链表相关oj题 -- 1

 目录

一.移除链表元素(203)

 二.反转链表(206)

1.思路1:

2.思路2:

 三.链表的中间结点(876)

思路:使用快慢指针。 

 四.链表中倒数第k个结点

 1.思路1:

2.思路2:

五.合并2个有序链表(21)

1.思路1:

2.思路2:

3.思路3:

一.移除链表元素(203)

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

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

输入:head = [], val = 1
输出:[]
示例 3:

输入:head = [7,7,7,7], val = 7
输出:[]
链接:https://leetcode.cn/problems/remove-linked-list-elements

 思路:定义一个cur的指针,去找值为val的结点,然后再定义一个prev去保存cur的前一个位置,每次当cur找到值为val的结点时,我们要让prev->next = val->next   ,  然后释放(free)掉cur找到的这个结点,  然后再让cur=prev->next

终止条件:就是当cur走到空就停止了

(要考虑第一个结点的值就是val的这种情况,就是头删了)

这里再演示一下头删 

 

  1. // 结构体
  2. //struct ListNode {
  3. // int val;
  4. //struct ListNode *next;
  5. //};
  6. struct ListNode* removeElements(struct ListNode* head, int val)
  7. {
  8. //找val的值为val的结点,把找到的结点free掉就可以了
  9. struct ListNode* prev=NULL;
  10. struct ListNode* cur=head;
  11. while(cur)
  12. {
  13. if(cur->val==val)
  14. {
  15. //1.头删
  16. if(cur==head)
  17. {
  18. head=head->next;
  19. free(cur);
  20. cur=head;
  21. }
  22. //2.中间删除
  23. else
  24. {
  25. prev->next=cur->next;
  26. free(cur);
  27. cur=prev->next;
  28. }
  29. }
  30. else
  31. {
  32. prev=cur;
  33. cur=cur->next;
  34. }
  35. }
  36. return head;
  37. }

 二.反转链表(206)

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

示例 1:
输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]


示例 2:
输入:head = [1,2]
输出:[2,1]
示例 3:

输入:head = []
输出:[]
链接:https://leetcode.cn/problems/reverse-linked-list

1.思路1:

 再原链表中进行反转,需要定义三个指针(prev  cur  next)

next负责记录下一个位置,cur负责反转,prev负责迭代记录。

最后返回我们的prev,就是我们反转后新的头。

这个是直到 cur走到空了,才停下来.

  1. //结构体
  2. // struct ListNode {
  3. // int val;
  4. // struct ListNode *next;
  5. //};
  6. struct ListNode* reverseList(struct ListNode* head)
  7. {
  8. struct ListNode* prev=NULL;
  9. struct ListNode* cur=head;
  10. struct ListNode* next=head;
  11. while(cur)
  12. {
  13. next=cur->next;
  14. //翻转
  15. cur->next=prev;
  16. //迭代往后走
  17. prev=cur;
  18. cur=next;
  19. }
  20. return prev;
  21. }

2.思路2:

 再创建一个新的链表来进行头插,把原链表中的结点从前往后遍历,依次头插到新的链表中,然后再返回我们新链表的头就可以了。

 

  1. //结构体
  2. // struct ListNode {
  3. // int val;
  4. // struct ListNode *next;
  5. //};
  6. struct ListNode* reverseList(struct ListNode* head)
  7. {
  8. //头插的思路
  9. struct ListNode* newhead=NULL;
  10. struct ListNode* cur=head;
  11. struct ListNode* next=head;
  12. while(cur)
  13. {
  14. next=cur->next;
  15. cur->next=newhead;
  16. newhead=cur;
  17. cur=next;
  18. }
  19. return newhead;
  20. }

3.思路3:

使用带有哨兵位的头结点来解决这道题,也是头插的思路

( 再创建一个新的链表来进行头插,把原链表中的结点从前往后遍历,依次头插到新的链表中,然后再返回我们新链表的头就可以了。)

  1. //结构体
  2. // struct ListNode {
  3. // int val;
  4. // struct ListNode *next;
  5. //};
  6. //使用带有哨兵位的头结点的链表来解决这道题
  7. //依旧还是头插的思路
  8. struct ListNode* reverseList(struct ListNode* head)
  9. {
  10. struct ListNode* newhead=(struct ListNode*)malloc(sizeof(struct ListNode));
  11. newhead->next=NULL;
  12. struct ListNode* cur=head;
  13. struct ListNode* next=head;
  14. while(cur)
  15. {
  16. next=cur->next;
  17. cur->next=newhead->next;
  18. newhead->next=cur;
  19. cur=next;
  20. }
  21. struct ListNode* list=newhead->next;
  22. free(newhead);
  23. return list;
  24. }

 三.链表的中间结点(876)

给定一个头结点为 head 的非空单链表,返回链表的中间结点。

如果有两个中间结点,则返回第二个中间结点。

示例 1:

输入:[1,2,3,4,5]
输出:此列表中的结点 3 (序列化形式:[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意,我们返回了一个 ListNode 类型的对象 ans,这样:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例 2:

输入:[1,2,3,4,5,6]
输出:此列表中的结点 4 (序列化形式:[4,5,6])
由于该列表有两个中间结点,值分别为 3 和 4,我们返回第二个结点。
链接:https://leetcode.cn/problems/middle-of-the-linked-list

思路:使用快慢指针。 

定义2个指针,slow和fast

slow一次走一步,fast一次走2步,链表的结点数有2种情况(奇数和偶数)

//1.如果是奇数个结点,那么应该是当fast到达链表尾部的时候,停下来

//2.如果是偶数个结点,那么应该是当fast指向空的时候,停下来

 所以停下来的条件是fast==NULL或者fast->next==NULL .

此时slow的位置就是链表的中间结点了。

  1. //结构体
  2. // struct ListNode {
  3. // int val;
  4. // struct ListNode *next;
  5. //};
  6. struct ListNode* middleNode(struct ListNode* head)
  7. {
  8. //定义快慢指针,一个一次走一步,一个一次走2步
  9. struct ListNode* slow=head;
  10. struct ListNode* fast=head;
  11. //1.如果是奇数个结点,那么应该是当fast到达链表尾部的时候,停下来
  12. //2.如果是偶数个结点,那么应该是当fast指向空的时候,停下来
  13. while(fast&&fast->next)
  14. {
  15. slow=slow->next;
  16. fast=fast->next->next;
  17. }
  18. return slow;
  19. }

 四.链表中倒数第k个结点

输入一个链表,输出该链表中倒数第k个结点。

示例一:

输入:

1,{1,2,3,4,5}

返回值:

{5}

 1.思路1:

// 1.fast先走k步,然后再让fast和slow一起走,当最后fast为空的时候,停下来

// 这个时候的slow就是链表中的倒数第k个结点

  1. //结构体
  2. // struct ListNode {
  3. // int val;
  4. // struct ListNode *next;
  5. // };
  6. struct ListNode* FindKthToTail(struct ListNode* pListHead, int k )
  7. {
  8. //1.fast先走k步,然后再让fast和slow一起走,当最后fast为空的时候,停下来
  9. //这个时候的slow就是链表中的倒数第k个结点
  10. struct ListNode* slow=pListHead;
  11. struct ListNode* fast=pListHead;
  12. while(k--)
  13. {
  14. if(fast==NULL)
  15. return NULL;
  16. else
  17. {
  18. fast=fast->next;
  19. }
  20. }
  21. while(fast)
  22. {
  23. fast=fast->next;
  24. slow=slow->next;
  25. }
  26. return slow;
  27. }

2.思路2:

// 2.fast先走k-1步,然后再让fast和slow一起走,当最后fast为链表的尾时,停下来

// 这个时候的slow就是链表中的倒数第k个结点 

  1. //结构体
  2. // struct ListNode {
  3. // int val;
  4. // struct ListNode *next;
  5. // };
  6. struct ListNode* FindKthToTail(struct ListNode* pListHead, int k )
  7. {
  8. //2.fast先走k-1步,然后再让fast和slow一起走,当最后fast为链表的尾时,停下来
  9. //这个时候的slow就是链表中的倒数第k个结点
  10. struct ListNode* slow=pListHead;
  11. struct ListNode* fast=pListHead;
  12. while(--k)
  13. {
  14. if(fast==NULL)
  15. {
  16. return NULL;
  17. }
  18. else
  19. {
  20. fast=fast->next;
  21. }
  22. }
  23. if(fast==NULL)
  24. return NULL;
  25. while(fast->next)
  26. {
  27. fast=fast->next;
  28. slow=slow->next;
  29. }
  30. return slow;
  31. }

五.合并2个有序链表(21)

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

示例1:

输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]
示例 2:

输入:l1 = [], l2 = []
输出:[]
示例 3:

输入:l1 = [], l2 = [0]
输出:[0]
链接:https://leetcode.cn/problems/merge-two-sorted-lists

1.思路1:

1.新建一个新的链表,然后把2个要合并的有序链表的结点进行比较,然后把比较之后小的那个结点尾插到新的链表里面。

  1. //结构体
  2. // struct ListNode {
  3. // int val;
  4. // struct ListNode *next;
  5. // };
  6. struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
  7. {
  8. if(list1==NULL)
  9. return list2;
  10. if(list2==NULL)
  11. return list1;
  12. struct ListNode* cur1=list1;
  13. struct ListNode* cur2=list2;
  14. struct ListNode* newhead=NULL;
  15. struct ListNode* tail=NULL;
  16. while(cur1&&cur2)
  17. {
  18. if(cur1->val<cur2->val)
  19. {
  20. if(newhead==NULL)
  21. {
  22. newhead=cur1;
  23. tail=cur1;
  24. cur1=cur1->next;
  25. }
  26. else
  27. {
  28. tail->next=cur1;
  29. tail=cur1;
  30. cur1=cur1->next;
  31. }
  32. }
  33. else
  34. {
  35. if(newhead==NULL)
  36. {
  37. newhead=cur2;
  38. tail=cur2;
  39. cur2=cur2->next;
  40. }
  41. else
  42. {
  43. tail->next=cur2;
  44. tail=cur2;
  45. cur2=cur2->next;
  46. }
  47. }
  48. }
  49. if(cur1!=NULL)
  50. {
  51. tail->next=cur1;
  52. }
  53. if(cur2!=NULL)
  54. {
  55. tail->next=cur2;
  56. }
  57. return newhead;
  58. }

2.思路2:

新建一个新的链表,然后把2个要合并的有序链表的结点进行比较,然后把比较之后小的那个结点尾插到新的链表里面。

2.和第一种方法相比就是在判断是否要头插的那里有点不一样,其他的思路和做法都是一样的。

  1. //结构体
  2. // struct ListNode {
  3. // int val;
  4. // struct ListNode *next;
  5. // };
  6. struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
  7. {
  8. if(list1==NULL)
  9. return list2;
  10. if(list2==NULL)
  11. return list1;
  12. struct ListNode* cur1=list1;
  13. struct ListNode* cur2=list2;
  14. struct ListNode* newhead=NULL;
  15. struct ListNode* tail=NULL;
  16. if(cur1->val<cur2->val)
  17. {
  18. newhead=cur1;
  19. tail=newhead;
  20. cur1=cur1->next;
  21. }
  22. else
  23. {
  24. newhead=cur2;
  25. tail=newhead;
  26. cur2=cur2->next;
  27. }
  28. while(cur1&&cur2)
  29. {
  30. if(cur1->val<cur2->val)
  31. {
  32. tail->next=cur1;
  33. tail=cur1;
  34. cur1=cur1->next;
  35. }
  36. else
  37. {
  38. tail->next=cur2;
  39. tail=cur2;
  40. cur2=cur2->next;
  41. }
  42. }
  43. if(cur1!=NULL)
  44. {
  45. tail->next=cur1;
  46. }
  47. if(cur2!=NULL)
  48. {
  49. tail->next=cur2;
  50. }
  51. return newhead;
  52. }

3.思路3:

新建一个新的链表,然后把2个要合并的有序链表的结点进行比较,然后把比较之后小的那个结点尾插到新的链表里面。

3.这个第三种方法的思路,简单来说和上面不同的点:就是新创建的是一个带有哨兵位的头结点的链表。

  1. //结构体
  2. // struct ListNode {
  3. // int val;
  4. // struct ListNode *next;
  5. // };
  6. struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
  7. {
  8. struct ListNode* newhead=(struct ListNode*)malloc(sizeof(struct ListNode));
  9. struct ListNode* tail=newhead;
  10. if(list1==NULL)
  11. return list2;
  12. if(list2==NULL)
  13. return list1;
  14. struct ListNode* cur1=list1;
  15. struct ListNode* cur2=list2;
  16. while(cur1&&cur2)
  17. {
  18. if(cur1->val<cur2->val)
  19. {
  20. tail->next=cur1;
  21. tail=cur1;
  22. cur1=cur1->next;
  23. }
  24. else
  25. {
  26. tail->next=cur2;
  27. tail=cur2;
  28. cur2=cur2->next;
  29. }
  30. }
  31. if(cur1!=NULL)
  32. {
  33. tail->next=cur1;
  34. }
  35. if(cur2!=NULL)
  36. {
  37. tail->next=cur2;
  38. }
  39. struct ListNode* list=newhead->next;
  40. free(newhead); // malloc 申请的空间,不使用了就要free(释放掉)
  41. return list;
  42. }

本文内容由网友自发贡献,转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号