文章目录

• • 一、删除单链表的节点
  • 二、合并两个排序链表
  • 三、两个链表的第一个公共节点
  • 四、链表中倒数第K个节点

一、删除单链表的节点

传送门
不多说

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* deleteNode(ListNode* head, int val) {if(head->val==val) return head->next;// 直接返回head的下一个 相当于头删了ListNode* prev=head;ListNode* cur=head->next;while(cur){if(cur->val==val){prev->next=cur->next;delete cur;return head;}cur=cur->next;prev=prev->next;}return head;}
};

二、合并两个排序链表

传送门
比较好想的，双指针分别比较两个链表的节点，把小的拿下来作为新的节点，当一条链表走完了，把另一个没有完的链表全部拿下来即可。
需要引入一个辅助节点，我们返回辅助节点的下一个即可

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode* tmp=new ListNode(-1);// 占位节点ListNode* head=tmp;while(l1 && l2){if(l1->val<=l2->val){tmp->next=l1;l1=l1->next;}else{tmp->next=l2;l2=l2->next;}tmp=tmp->next;}// 现在有一个链表走完了，但是不知是哪一个if(!l1){tmp->next=l2;}if(!l2){tmp->next=l1;}return head->next;}
};

三、两个链表的第一个公共节点

传送门
这是一个很牛逼的解法，双指针！！

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode *node1 = headA;ListNode *node2 = headB;while (node1 != node2) {node1 = node1 != NULL ? node1->next : headB;node2 = node2 != NULL ? node2->next : headA;}return node1;}
};

四、链表中倒数第K个节点

传送门

法一：暴力遍历
第一次遍历统计长度，第二次找正数第n-k个节点

法二：双指针
快指针先走k步，然后快慢指针同时走，一次走一步，直到快指针走到空

class Solution {
public:ListNode* getKthFromEnd(ListNode* head, int k) {ListNode* first=head, *last=head;while(k--){first=first->next;}while(first!=nullptr){first=first->next;last=last->next;}return last;}
};