ToB企服应用市场:ToB评测及商务社交产业平台

标题: 【数据结构初阶】单链表经典算法题十道（详解+图例）—得道飞升（上篇） [打印本页]

---

作者: 张裕    时间: 2024-8-2 13:33
标题: 【数据结构初阶】单链表经典算法题十道（详解+图例）—得道飞升（上篇）
目录
1、移除元素
2、反转链表
3、链表的中心节点
4、合并两个有序链表
Relaxing Time！！！
————————————————  天气之子·幻  ————————————————

---

1、移除元素

思绪：
创建一个新链表（newhead，newtail），遍历原链表，把不等于 val 的结点尾插到新链表中。

1. /**
2. * Definition for singly-linked list.
3. * struct ListNode {
4. *     int val;
5. *     struct ListNode *next;
6. * };
7. */
8. typedef struct ListNode ListNode;
9. struct ListNode* removeElements(struct ListNode* head, int val) {
10.     //创建新链表
11.     ListNode* newhead;ListNode* newtail;
12.     newhead=newtail=NULL;
13.     //遍历数组
14.     ListNode* pcur=head;
15.     while(pcur)
16.     {
17.         if(pcur->val!=val)
18.         {
19.             //又分两种情况，链表为空，不为空
20.             if(newhead==NULL)
21.             {
22.                 newtail=newhead=pcur;
23.             }
24.             else
25.             {
26.                 newtail->next=pcur;
27.                 newtail=newtail->next;
28.             }
29.         }
30.         pcur=pcur->next;
31.     }
32.     //[7,7,7,7,7]，val=7 ，这种情况下，newtail=NULL，newtail->next=NULL，此时newtail不能解引用，所以加上if条件
33.     if(newtail)               
34.         newtail->next=NULL;
35.     return newhead;
36. }

复制代码

留意：
当原链表为空时，newhead = newtail = pcur； 
在实例中，最后一个5结点被尾插到新链表中时，5结点的next指针指向的仍然是背面的6结点，所以最后返回的时间结果里面含有6，所以我们把最后一个等于val结点的next指针指向NULL即可！

2、反转链表

新奇思绪：

1. /**
2. * Definition for singly-linked list.
3. * struct ListNode {
4. *     int val;
5. *     struct ListNode *next;
6. * };
7. */
8. typedef struct ListNode ListNode;
9. struct ListNode* reverseList(struct ListNode* head) {
10.     //链表也有可能是空链表
11.     if(head==NULL)
12.     {
13.         return head;
14.     }
15.     //定义三个指针变量
16.     ListNode* n1,*n2,*n3;
17.     n1=NULL;n2=head;n3=n2->next;
18.     while(n2)
19.     {
20.         n2->next=n1;
21.         n1=n2;
22.         n2=n3;
23.         if(n3)
24.         n3=n3->next;
25.     }
26.     return n1;
27. }

复制代码

3、链表的中心节点

思绪： 
奇数个结点

偶数个结点 

1. /**
2. * Definition for singly-linked list.
3. * struct ListNode {
4. *     int val;
5. *     struct ListNode *next;
6. * };
7. */
8. typedef struct ListNode ListNode;
9. struct ListNode* middleNode(struct ListNode* head) {
10.     ListNode* slow=head;
11.     ListNode* fast=head;
13.     //while(fast->next&&fast)错误，不可互换顺序，当为偶数个结点时，fast==NULL循环结束，但是while
14.       循环内会先判断fast->next,空指针不能解引用，会报错
16.     while(fast&&fast->next)
17.     {
18.         //慢指针每次走一步
19.         //快指针每次走两步
20.         slow=slow->next;
21.         fast=fast->next->next;
22.     }
23.     //此时slow指向的结点恰好是中间结点
24.     return slow;
25. }

复制代码

快慢指针为什么可以找到中心结点？（快慢指针的原理）
慢指针每次走一步，快指针每次走两步，当快指针走到链表的尾结点时，假设链表的长度为n，快指针走的路程是慢指针的两倍，2*慢=快，即慢指针走的路程是n/2。

4、合并两个有序链表

思绪：
创建一个新链表，newhead，newtail 指向新链表的头结点，界说两个指针分别指向原链表的头结点，两个指针指向的数据比较大小，谁小谁尾插到新链表里面。思绪清晰，不过要留意许多细节，直接上代码：

1. /**
2. * Definition for singly-linked list.
3. * struct ListNode {
4. *     int val;
5. *     struct ListNode *next;
6. * };
7. */
8. typedef struct ListNode ListNode;
9. struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
11.     //处理原链表为空链表的情况
12.     if(list1==NULL)
13.     {
14.         return list2;
15.     }
16.     if(list2==NULL)
17.     {
18.         return list1;
19.     }
21.     //创建一个新链表
22.     ListNode* newhead=NULL;
23.     ListNode* newtail=NULL;
25.     //创建两个指针分别指向两个链表的头结点来遍历原链表
26.     ListNode* l1=list1;
27.     ListNode* l2=list2;
28.    
29.     while(l1&&l2)
30.     {
31.         if(l1->val<l2->val)
32.         {
33.             //l1尾插到新链表
34.             if(newtail==NULL)
35.             {
36.                 newtail=newhead=l1;
37.             }
38.             else
39.             {
40.                 newtail->next=l1;
41.                 newtail=newtail->next;
42.             }
43.             l1=l1->next;
44.         }
45.         else
46.         {
47.             //l2尾插到新链表
48.             if(newhead==NULL)
49.             {
50.                 newtail=newhead=l2;
51.             }
52.             else
53.             {
54.                 newtail->next=l2;
55.                 newtail=newtail->next;
56.             }
57.              l2=l2->next;
58.         }
59.     }
60.     //出循环，要么l1==NULL，要么l2==NULL
61.         if(l1)
62.             newtail->next=l1;  想想这里为啥不用while循环？
63.         if(l2)
64.             newtail->next=l2;
65.     return newhead;
66. }

复制代码

1. //优化过后，申请一个不为空的链表，就无需再判断新链表是否为空，最后不要忘记free
2. /**
3. * Definition for singly-linked list.
4. * struct ListNode {
5. *     int val;
6. *     struct ListNode *next;
7. * };
8. */
9. typedef struct ListNode ListNode;
10. struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
12.     //链表为空的情况
13.     if(list1==NULL)
14.     {
15.         return list2;
16.     }
17.     if(list2==NULL)
18.     {
19.         return list1;
20.     }
21.    
22.     //创建一个新链表
23.     ListNode* newhead,*newtail;
24.      newhead=newtail=(ListNode*)malloc(sizeof(ListNode));
25.     //定义两个指针来遍历数组
26.     ListNode* l1=list1;
27.     ListNode* l2=list2;
29.     while(l1&&l2)
30.     {
31.         if(l1->val<l2->val)
32.         {
33.             newtail->next=l1;
34.             l1=l1->next;
35.             newtail=newtail->next;
36.         }
37.         else
38.         {
39.             newtail->next=l2;
40.             l2=l2->next;
41.             newtail=newtail->next;
42.         }
43.     }
44.     if(l1)
45.         newtail->next=l1;
46.     if(l2)
47.         newtail->next=l2;
49.     ListNode* ret=newhead->next;
50.     free(newhead);
51.     newhead=NULL;
52.     return ret;
53.    
54. }

复制代码

---

完—

Relaxing Time！！！


————————————————  天气之子·幻  ————————————————



天气之子·幻_TypeD_高音质在线试听_天气之子·幻歌词|歌曲下载_酷狗音乐酷狗音乐为您提供由TypeD演唱的高清音质无损天气之子·幻mp3在线听,听天气之子·幻,只来酷狗音乐!

https://t4.kugou.com/song.html?id=b43Kh7aCPV2

至此竣事——
再见——




免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4