链表专项练习(四)
一、剑指 Offer 22. 链表中倒数第k个节点
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。 例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
示例： 给定一个链表: 1->2->3->4->5, 和 k = 2. 返回链表 4->5.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* getKthFromEnd(struct ListNode* head, int k){
struct ListNode*fast=head;
struct ListNode*slow=head;
if(head==NULL)
{
return NULL;
}
while(k--)
{
if(fast!=NULL)
{
fast=fast->next;
}
else
{
return NULL;
}
}
while(fast!=NULL)
{
slow=slow->next;
fast=fast->next;
}
return slow;
}
在这里插入图片描述
二、21. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1： 输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4] 示例 2： 输入：l1 = [], l2 = [] 输出：[] 示例 3： 输入：l1 = [], l2 = [0] 输出：[0]
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
struct ListNode*l1=list1;
struct ListNode*l2=list2;
struct ListNode*head=NULL;
struct ListNode*tail=NULL;
if(l1==NULL)
{
return l2;
}
if(l2==NULL)
{
return l1;
}
while(l1&&l2)
{
if(l1->val<l2->val)
{
if(tail==NULL)
{
head=l1;
tail=l1;
}
else
{
tail->next=l1;
tail=tail->next;
}
l1=l1->next;
}
else
{
if(tail==NULL)
{
head=l2;
tail=l2;
}
else
{
tail->next=l2;
tail=tail->next;
}
l2=l2->next;
}
}
if(l1!=NULL)
{
tail->next=l1;
}
if(l2!=NULL)
{
tail->next=l2;
}
return head;
}
在这里插入图片描述
三、206. 反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
在这里插入图片描述
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head){
struct ListNode*cur=head;//头插法
struct ListNode*newnode=NULL;
while(cur!=NULL)
{
struct ListNode*next=cur->next;//将cur后一个节点存起来
cur->next=newnode;//将cur头插新节点
newnode=cur;
cur=next;
}
return newnode;
}/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head){
if(head==NULL)
{
return NULL;
}
struct ListNode*n1=NULL;//逆置链表
struct ListNode*n2=head;
struct ListNode*n3=head->next;
while(n2!=NULL)
{
n2->next=n1;
n1=n2;
n2=n3;
if(n3!=NULL)
{
n3=n3->next;
}
}
return n1;
}
在这里插入图片描述
四、203. 移除链表元素
给你一个链表的头节点 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 输出：[]
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeElements(struct ListNode* head, int val){
if(head==NULL)
{
return NULL;
}
struct ListNode*cur=head;
struct ListNode*prev=NULL;
while(cur!=NULL)
{
if(head->val==val)//考虑头删
{
head=head->next;
cur=head;
}
else
{
if(cur->val==val)//如果是在中间删或者尾删
{
prev->next=cur->next;
cur=prev->next;
}
else
{
prev=cur;//如果不是就向后走
cur=cur->next;
}
}
}
return head;
}
在这里插入图片描述
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-09-22，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
