@TOC
一、剑指 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; }
在这里插入图片描述
