【数据结构】单链表OJ题(一)

🔥博客主页： 小羊失眠啦.
🎥系列专栏：《C语言》 《数据结构》 《Linux》《Cpolar》
❤️感谢大家点赞👍收藏⭐评论✍️

---

前言

在上一期中我们介绍了单链表，也对单链表的实现进行具体的了解，接下来我们开始单链表的练习，对单链表更深层的理解，让小伙伴们灵活的使用单链表，话不多说，开造~

---

一、移除链表元素

💭方法一：

我们使用两个指针遍历数组，遇到与 val 相同的结点时，就删除这个节点。我们在思考问题时要想全面，当要删除头节点时，常规方法就无法实现，对于删除头节点要做单独处理。

常规删除：

头节点删除：

思路：(1)首先给出判断cur是否是空的，不是空的之后，判断是否有val，有的话就判断是否在头部，是的话一种情况，不是的话，又是一种情况。（2）第一种情况，题意所给出的情况；第二种情况，中间连续个value（前两种可以合并）；第三种情况，一开始就出现6或者连续个6；第四种情况：空的

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

💭方法二：

我们通过遍历，把节点的数据域不等于val的节点尾接到新的链表中。我们要考虑第一个节点是不是要删除的。最后一个节点的指针域置空要放在循环结束后，判断tail是否为空指针。

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

---

二、寻找链表中间结点

我们可以定义两个指针，快指针一次走两步，慢指针一次走一步，当快指针走到结尾时，慢指针正好走了一半，这样我们就可以找到中间节点。

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

---

三、输出链表倒数第k个结点

我们可以参考上一题的方法，同样定义快慢指针，先让快指针走k步，然后再同时走，走到fast为空指针就找了倒数第k个节点。有可能链表没有k个节点，所以我们要加入判断。

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {struct ListNode* slow=pListHead,*fast=pListHead;while(k--){if(fast==NULL){return NULL;}fast=fast->next;}while(fast){slow=slow->next;fast=fast->next;}return slow;
}

---

四、反转单链表

💭方法一：

我们定义三个指针n1,n2,n3，来改变节点链接的顺序。将头节点变为尾节点，当n2为空指针时，n1就为链表的头节点，只需返回n1就可以。两个指针倒方向，一个指针保持下一个。

struct ListNode* reverseList(struct ListNode* head) {struct ListNode* n1=NULL,*n2=head,*n3=NULL;if(head==NULL)return head;while(n2){n3=n2->next;n2->next=n1;n1=n2;n2=n3;}return n1;
}

💭方法二：

将链表的节点一个一个拿下来，进行头插。这里要注意赋值的顺序。

struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* cur=head;struct ListNode* newnode=NULL;while(cur){//保存节点struct ListNode* next=cur->next;//头插cur->next=newnode;newnode=cur;cur=next;}return newnode;
}

---

五、合并两个有序链表

思路：每次取小的节点尾插到新的节点

注意：其中一个为空的情况要注意

💭代码一：（不带头）

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{if(list1==NULL)return list2;if(list2==NULL)return list1;struct ListNode* head=NULL;struct ListNode* tail=NULL;while(list1&&list2){if((list1->val) < (list2->val)){if(tail==NULL){head=list1;tail=list1;}else{tail->next=list1;tail=list1;}list1=list1->next;}else{if(tail==NULL){head=list2;tail=list2;}else{tail->next=list2;tail=list2;}list2=list2->next;}}if(list1)tail->next=list1;if(list2)tail->next=list2;return head;
}

有头单链表：head->next指的是第一个节点的地址（带头，相当于开头多了一个节点，但是节点里面的val不确定，next指向下一个节点）； 无头单链表：head指的是第一个节点的地址； OJ题默认不带头

💭代码二：（带头）

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));//创建一个头struct ListNode* tail = head;head->next = NULL;//就是含有值的节点的第一个while (list1 && list2){struct ListNode* next1 = list1->next;struct ListNode* next2 = list2->next;if ((list1->val) < (list2->val)){tail->next = list1;tail = list1;list1 = next1;}else{tail->next = list2;tail = list2;list2 = next2;}}if (list1 != NULL){tail->next = list1;}if (list2 != NULL){tail->next = list2;}struct ListNode* list = head->next;free(head);return list;
}

思路：每次取小的节点尾插到新的节点

注意：mallloc的一个地址，到最后要进行释放。

本次的内容到这里就结束啦。希望大家阅读完可以有所收获，同时也感谢各位铁汁们的支持。文章有任何问题可以在评论区留言，小羊一定认真修改，写出更好的文章~~