如何高效解决链表中的插入、删除、查找等操作难题？

本文共计1507个文字，预计阅读时间需要7分钟。

题目1：删除链表元素题目：给你一个链表的头节点 `head` 和一个整数 `val`，请删除链表中所有满足 `Node.val=val` 的节点，并返回新的头节点。解题思路1：我们首先遍历链表，找到所有满足条件的节点并将其删除。我们可以使用一个哑节点 `dummy` 作为辅助，来简化边界情况的处理。哑节点的下一个节点指向头节点，这样我们就可以直接操作头节点而不需要额外判断。在遍历过程中，如果当前节点的下一个节点满足删除条件，我们就更新当前节点的 `next` 指针，跳过被删除的节点。最后，返回哑节点的下一个节点作为新的头节点。

题目1：力扣203题移除链表元素

题目：

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

解题思路1：

我们找到符合规则的节点并且直接删除

画图的方式解释

以此不断的继续下去直到完成链表特定值的删除

struct ListNode* removeElements(struct ListNode* head, int val) { //对于理解这道题，我没有理解的地方在于如何做到让一个节点指针在前一个节点指针在后 //还有就是我们对于head就是要删除的节点要特殊处理 struct ListNode* prev = NULL;//这个指针就是后指针 struct ListNode* cur = head; while (cur) { if (head->val == val)//这里我们要对特殊情况做出处理 { struct ListNode* tmp = head; head = head->next; cur = head; free(tmp); } else if (cur->val == val) { struct ListNode* tmp = cur;//储存要删除的节点地址 cur = cur->next;//再将cur移动 prev->next = cur;//这里完成连接 free(tmp);//最后释放 } else//如果该节点不是要删除的节点 { prev = cur;//先将这个节点交给prev cur = cur->next;//在让cur前移 } } return head;//最后返回 }

下面的是方法二：

struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode* newnode = NULL, *cur = head,*tail = NULL; //这里得newnode是我们创建得一个新的头节点 //然后tail就是用于找到新创建的链表得尾部的 while (cur) { if (cur->val != val)//开始尾插 //但是尾插我们要解决newnode一开始指向得是null的问题 { if (newnode == NULL) { newnode =tail = cur; cur = cur->next; } else { tail->next = cur; tail = tail->next; cur = cur->next; } tail->next = NULL; } else { struct ListNode* tmp = cur; cur = cur->next; free(tmp); } } return newnode; }

即每一次都将不是val值得节点尾插到新链表然后删除是val的节点就可以了

题目二：力扣206题反转一个链表

题目：给你单链表的头节点head，请你反转链表，并返回反转后的链表。

解题思路：我们可以将每一个节点头插到一个新链表的头节点就可以了。

struct ListNode* reverseList(struct ListNode* head) { if(head ==NULL) { return NULL; } struct ListNode* newnode = NULL; struct ListNode* cur = head; while(cur) { struct ListNode* tmp = cur;先创建一个节点用以保存要头插的节点 cur = cur->next;//将cur后移一个节点 tmp->next = newnode;//将newnode之前的节点连接到tmp节点的后面 newnode = tmp;//在改变newnode } return newnode; }

题目三：3.给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点

这道题我们要考虑两种情况一种情况是节点数量为奇数一种情况是节点数量为偶数。

对于如何找到中间节点我们可以使用快慢指针的方法即一个指针一次只跳过一个节点，一个指针一个跳过两个节点

然后我们通过图像可以知道

struct ListNode* middleNode(struct ListNode* head) { struct ListNode* fast = head,*slow = head; while(fast&&fast->next)//当fast或是fast->next任意一个为空则循环结束 { fast = fast->next->next;//一次走两步 slow = slow->next; } return slow; }

题目四：牛客输入一个链表，输出该链表中倒数第k个结点

解题思路:

还是使用的是快慢指针我们可以先让fast指针移动k个节点，然后再让fast和slow一起移动

最后当fast指向空的时候返回slow就可以了

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { struct ListNode* fast = pListHead,*slow = pListHead; if(pListHead == NULL)//如果传过来的本身就是一个空指针那么返回空就可以了 { return NULL; } while(k)//先开始移动fast指针 { k--; fast = fast->next; if(fast==NULL)//为了防止过量移动当fast为空的时候就直接结束循环 { break; } } if(k!=0)//循环结束以后如果k不为0代表要返回的节点超出链表范围可以返回空了 { return NULL; } while(fast) { fast = fast->next; slow = slow->next; } return slow; }

题目五：力扣21题

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

思路选择链表里面值小的尾插到新链表即可

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { if(list1==NULL)//如果list1为空 { return list2;//直接返回list2 } if(list2==NULL) { return list1;//理由和上面的一样 } struct ListNode* newnode = NULL; struct ListNode* tail = NULL; while(list1&&list2)//当任意一个节点尾插完毕的时候我们就要停止循环 { if(list1->val<list2->val) { if(newnode==NULL)//如果此时的newnode为空指针的话我们就要让newnode改变一下 { newnode = tail = list1; list1 = list1->next; } else//开始尾插 { tail->next = list1; tail = tail->next; list1 = list1->next; } } else { if(newnode==NULL) { newnode = tail = list2; list2 = list2->next; } else { tail->next = list2; tail = tail->next; list2 = list2->next; } } } if(list1)//这里就是list1后面还有未插入的数据 { tail->next = list1; } if(list2)//这里就是list2后面还有未插入的数据 { tail->next = list2; } return newnode; }