链表题（2）

链表题（2）"/>

链表题（2）

链表题

今天给大家带来道链表题的练习

移除链表元素

这道题上篇文章已经解决过一次，这次我们换一个思路来解决这个问题。
先把链接给大家奉上：

/

题目描述：
给你一个链表的头节点 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
输出：[]

提示：

列表中的节点数目在范围 [0, 104] 内
1 <= Node.val <= 50
0 <= val <= 50

思路：
这次，我们把不需要删除的节点都让一个新的链表指向，最后返回新的链表头接待你，需要删除的释放掉即可。

struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode* newnode=NULL;//新链表头节点指针struct ListNode* tail=NULL;//新链表指针struct ListNode* cur=head;//cur循环链表指针while(cur)//遍历原链表{if(cur->val!=val)//不需要删除的节点{if(tail==NULL)//第一次进入循环{tail=cur;//tail和newnode都指向头节点newnode=cur;cur=cur->next;//链表移动}else//非第一次进入{tail->next=cur;//新链表指针tail的next指向curtail=tail->next;//tail指针靠后移动cur=cur->next;//原链表继续移动遍历}}else//需要删除的节点{struct ListNode* tmp=cur;//将该节点赋给临时指针tmp cur=cur->next;//原链表向后移动遍历free(tmp);//释放掉该临时指针tmp}}if(tail)//只要原链表不为空就进行该操作tail->next=NULL;//将最后一个节点的next赋值为空指针return newnode;//返回新的头节点
}

链表中倒数第k个结点

时间限制：1秒 空间限制：64M
知识点
链表 双指针
描述：
输入一个链表，输出该链表中倒数第k个结点。
示例1
输入：
1,{1,2,3,4,5}
返回值：
{5}

题目链接：

=13&&tqId=11167&rp=2&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

首先这道题的函数是接受一个链表，和一个整形k，返回倒数第k个节点，我们用双指针的思路很好解决，用快慢指针就可以解决，我们可以先让快指针走k步，然后快指针和慢指针一起走完整个链表，此时慢指针比快指针少走了k步，那么慢指针此时指向的节点就是倒数第k个节点。

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {if(PListHead==NULL)//如果pListHead为空，返回空指针return NULL;struct ListNode* fast=pListHead;//快慢指针都指向该链表struct ListNode* slow=pListHead;while(k--)//快指针先走k步{if(fast==NULL)//如果快指针为空指针说明遍历完该链表，k超出了整个链表的节点返回空指针return NULL;fast=fast->next;//快指针向后移动}while(fast)//快指针遍历完，慢指针开始移动{fast=fast->next;//快指针移动slow=slow->next;//慢指针移动}//循环结束时，快指针遍历完成，慢指针比快指针少走k步，此时慢指针指向倒数第k个节点return slow;//返回此时慢指针所指向的节点。
}

这个代码十分的简单，具体解释看注释就可以了。

（最后，题目来自牛客网，和力扣网，侵权联系，作者必删。）