【数据结构】链表-C语言版（二）-阿里云开发者社区

【数据结构】链表-C语言版（二）

2023-02-07 116

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【数据结构】链表-C语言版

链表应用OJ题

1.删除链表中等于给定值val的所有节点，OJ链接

分析：

（1）要删除某一结点，需要保存该结点的前一个结点（删除当前节点后，前一结点应指向当前结点的下一结点），同时需要保存当前结点的下一结点（删除当前结点后，能够继续向后访问该链表）

（2）操作：

遍历链表，如果当前结点值==val，就保存当前结点的下一个结点，前一结点指向当前结点的下一结点，释放当前结点，当前结点指向下一结点；

如果当前结点值!=val，前一结点挪到当前结点位置，当前结点挪到下一结点位置。需要考虑特殊情况，第一个结点值 == val时，此时prev=NULL需要特殊处理。

不带哨兵位头结点解法：

1. /**
2.  * Definition for singly-linked list.
3.  * struct ListNode {
4.  *     int val;
5.  *     struct ListNode *next;
6.  * };
7.  */
8. 
9. struct ListNode* removeElements(struct ListNode* head, int val){
10. 
11.     struct ListNode* prev = NULL;
12.     struct ListNode* cur = head;
13. 
14.     while(cur)
15.     {
16.         if(cur->val == val)//找到了
17.         {
18.             struct ListNode* next = cur->next;//要free(cur)，就必须要先保存cur的下一个结点，否则无法继续访问下一结点
19.             if(prev == NULL)//cur是头，要删除的结点在第一个位置
20.             {
21.                 free(cur);
22.                 head = next;
23.                 cur = next;
24.             }
25.             else
26.             {
27.                 prev->next = next;
28.                 free(cur);
29.                 cur = next;
30.             }   
31.         }
32.         else
33.         {
34.             prev = cur;
35.             cur = cur->next;    
36.         }
37.       
38.     }   
39.     return head;
40. }

带哨兵位头结点解法：

1. /**
2.  * Definition for singly-linked list.
3.  * struct ListNode {
4.  *     int val;
5.  *     struct ListNode *next;
6.  * };
7.  */
8. 
9. struct ListNode* removeElements(struct ListNode* head, int val)
10. {
11.     struct ListNode* guardHead = (struct ListNode*)malloc(sizeof(struct ListNode));
12.     guardHead->next = head;
13. 
14.     struct ListNode* prev = guardHead;
15.     struct ListNode* cur = head;
16. 
17.     while (cur)
18.     {
19.         if (cur->val == val)
20.         {
21.             struct ListNode* next = cur->next;
22.             prev->next = next;
23.             free(cur);
24.             cur = next;
25.         }
26.         else
27.         {
28.             prev = cur;
29.             cur = cur->next;
30.         }
31.     }
32. 
33.     head = guardHead->next;
34.     free(guardHead);
35.     guardHead = NULL;
36.     return head;
37. 
38. }

2.反转一个单链表 OJ链接

分析：

解法一：如果只定义两个节点，当n2指向n1时，n2的下一个结点就找不到了。因此要定义3个节点，n1和n2用于翻转，n3用于迭代：n1指向NULL，n2指向n1，n3用于记录n2的下一个结点。

1. /**
2.  * Definition for singly-linked list.
3.  * struct ListNode {
4.  *     int val;
5.  *     struct ListNode *next;
6.  * };
7.  */
8. 
9. struct ListNode* reverseList(struct ListNode* head)
10. {
11.     if(head == NULL || head->next == NULL)
12.     {
13.         return head;
14.     }
15.     
16.     struct ListNode* n1 = NULL,*n2 = head,*n3 = head->next;
17.     while(n2)
18.     {
19.         n2->next = n1;
20.         n1 = n2;
21.         n2 = n3;
22.         if(n3)
23.         {
24.             n3 = n3->next;
25.         }
26.     }
27.     return n1;
28. }

解法二：头插法，依次取原链表中的节点头插到新节点

1. /**
2.  * Definition for singly-linked list.
3.  * struct ListNode {
4.  *     int val;
5.  *     struct ListNode *next;
6.  * };
7.  */
8. 
9. struct ListNode* reverseList(struct ListNode* head)
10. {
11.     struct ListNode* cur = head;
12.     struct ListNode* newHead = NULL;
13. 
14.     while(cur)
15.     {
16.         struct ListNode* next = cur->next;
17. 
18.         cur->next = newHead;
19.         newHead = cur;
20.         cur = next;
21.     }
22.     return newHead;
23. }

3.链表的中间结点 OJ链接

分析：只能遍历一遍，可以用快慢指针，慢指针每次走一步，快指针每次走两步

1. /**
2.  * Definition for singly-linked list.
3.  * struct ListNode {
4.  *     int val;
5.  *     struct ListNode *next;
6.  * };
7.  */
8. 
9. 
10. struct ListNode* middleNode(struct ListNode* head)
11. {
12.     struct ListNode* slow = head;
13.     struct ListNode* fast = head;
14. 
15.     while(fast && fast->next)
16.     {
17.         slow = slow->next;
18.         fast = fast->next->next;
19.     }
20. 
21.     return slow;
22. }

4.输出链表倒数第k个结点，OJ链接

分析：如何找倒数第k个结点，可以使用快慢指针，让快指针先走k步，再让慢指针开始走，此时快慢指针相差k步，然后快慢指针一起向后移动，等快指针移动到链表末尾NULL时，慢指针的位置就是倒数第k个结点位置。

1. struct ListNode 
2. {
3.  int val;
4.  struct ListNode *next;
5. };
6. 
7. struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) 
8. {
9.     
10.     if(pListHead == NULL)
11.     {
12.         return NULL;
13.     }
14. 
15.     struct ListNode* slow = pListHead;
16.     struct ListNode* fast = pListHead;
17.     
18.     while(k--)
19.     {
20.         if(fast == NULL)
21.         {
22.             return NULL;
23.         }
24.         fast = fast->next;
25.     }
26.     
27.     while(fast)
28.     {
29.         slow = slow->next;
30.         fast = fast->next;
31.     }
32.     
33.     return slow;
34. }

5.合并两个有序链表 OJ链接

分析：尾插法，找第一个结点小的链表当作新表头，找尾比较麻烦，需要遍历，因此直接定义一个尾节点tail，每次让tail指向刚插入的节点，当有一个链表走完时就停下，再把没走完的链表全部连接到tail上。

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

6.编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 OJ链接

分析：申请两个链表，一个放比x小的节点，一个放比x大的节点，最后将大链表链接在小链表末尾即可。

1. 
2. struct ListNode {
3.     int val;
4.     struct ListNode *next;
5.     ListNode(int x) : val(x), next(NULL) {}
6. };
7. 
8. class Partition {
9. public:
10.     ListNode* partition(ListNode* pHead, int x) {
11.         // 有头指针
12.         struct ListNode* lessHead,* lessTail,*greaterHead,*greaterTail;
13.         lessHead = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode));
14.         greaterHead = greaterTail = (struct ListNode*)malloc(sizeof(struct ListNode));
15.       
16.         lessTail->next = NULL;
17.         greaterTail->next = NULL;
18.       
19.         struct ListNode *cur = pHead;
20.       
21.         while(cur)
22.         {
23.             if(cur->val<x)
24.             {
25.                 lessTail->next = cur;
26.                 lessTail = lessTail->next;
27.             }
28.             else
29.             {
30.                 greaterTail->next = cur;
31.                 greaterTail = greaterTail->next;
32.             }
33.             cur = cur->next;
34.         }
35.       
36.         lessTail->next = greaterHead->next;
37.         greaterTail->next = NULL;
38.       
39.         pHead = lessHead->next;
40.         free(lessHead);
41.         free(greaterHead);
42.       
43.         return pHead;
44.     }
45. };

【数据结构】链表-C语言版（二）

链表应用OJ题

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【数据结构】链表-C语言版（二）

链表应用OJ题

热门文章

最新文章

相关课程

相关电子书