10
链表专项练习(四)_萌新的日常的技术博客_51CTO博客
source link: https://blog.51cto.com/u_15787387/5688162
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
链表专项练习(四)
精选 原创一、剑指 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;
}
- 赞
- 收藏
- 评论
- 分享
- 举报
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK