「算法刷题」链表的删除、反转、两数相加的LeetCode题目实现

[TOC]

​ 本文主要记录链表的相关LeetCode题目的实现代码，直接给出本文各个题目的答案，供有需求的读者学习或复制。

一、删除链表的LeetCode题目

1、删除链表中的特定值

203. 移除链表元素（简单难度）

剑指 Offer 18. 删除链表的节点（简单难度）

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        //新建虚拟头结点
        ListNode * myHead = new ListNode(0);
        myHead->next=head;
        //双指针
        ListNode* prev=myHead;//慢指针负责删除节点
        ListNode* cur=prev->next;//当前节点负责确定是否需要删除
        while (cur) {
            // 如果满足条件则执行删除操作；否则慢指针前进一步
            if(cur->val == val) {
                prev->next = cur->next;//删除快指针
            } else {
                prev = cur;//慢指针前进一步
            }
            cur = cur->next;//快指针前进一步
        }
        return myHead->next;
    }
};

83. 删除排序链表中的重复元素（简单难度）

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        // 新建虚拟头结点
        ListNode * myHead=new ListNode(-101);
        myHead->next=head;
        // 快慢指针扫描单链表
        ListNode * prev=myHead;//负责删除
        ListNode * cur=head; // 负责遍历和确定
        while(cur!=nullptr){
            if(cur->val==prev->val){
                prev->next=cur->next;
            }
            else{
                prev=prev->next;
            }
            cur=cur->next;
        }
        return myHead->next;
    }
};

2、只给出待删除元素，实现删除效果

237. 删除链表中的节点（简单难度）

面试题 02.03. 删除中间节点（简单难度）

class Solution {
public:
    void deleteNode(ListNode* node) {
        // node是要删除的节点，将其伪装成下一个节点son
        ListNode* son=node->next;
        node->val=son->val;//伪装其val
        node->next=son->next;//伪装其next
    }
};

3、删除链表中的倒数第N个节点

19. 删除链表的倒数第 N 个结点（中等难度）

剑指 Offer 22. 链表中倒数第k个节点（简单难度）

剑指 Offer II 021. 删除链表的倒数第 n 个结点（中等难度）

方式一：计数法

class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        // 循环单链表获取len
        int len=0;
        ListNode* p=head;
        while(p){
            p=p->next;
            len++;
        }
        // 循环单链表找到第len-k个元素（倒数第k个==正数第len-k+1）
        int i=0;
        p=head;
        while(p&&i<len-k){
            p=p->next;
            i++;
        }
        return p;
    }
};

方式二：快慢指针法

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* fast=head;
        ListNode* slow=head;
        //先让fast走n步，此时fast可能不存在
        for(int i=0;i<n;i++){
            fast=fast->next;
        }
        //若fast不存在，说明n>链表的长度，则删除掉头结点，保留头结点之后的节点
        if(!fast){
            return head->next;
        }
        //若fast存在，同时遍历
        while(fast->next){
            slow=slow->next;
            fast=fast->next;
        }
        slow->next=slow->next->next;
        
        return head;
    }
};

2095. 删除链表的中间节点（中等难度）

快慢指针法：

class Solution {
public:
    ListNode* deleteMiddle(ListNode* head) {
        ListNode* p=head;
        int len=0;
        while(p){
            p=p->next;
            len++;
        }
        if(len==1) return nullptr;
        if(len==2) {
            head->next=nullptr;
            return head;
        }
        int i=0;
        p=head;
        while(p&&i<len/2-1){
            p=p->next;
            i++;
        }
        p->next=p->next->next;
        return head;
    }
};

4、删除链表中的一段特殊序列

82. 删除排序链表中的重复元素 II（中等难度）

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        // 新建虚拟头结点
        ListNode * myHead=new ListNode(-101);
        myHead->next=head;
        // 快慢指针扫描单链表删除重复元素
        ListNode* p=myHead;//遍历指针，负责遍历
        ListNode * left,*right;//快慢指针，
        while(p->next!=nullptr){
            left=p->next;//保留起始指针
            right=left; //一开始快慢指针相同，比p多一步
            // 尝试移动right,如果right->next存在且和right相同就移动一步，最终right将指向最后一个相同的数
            while(right->next && right->next->val==right->val)
                right=right->next;
            // 如果left==right，说明right没有移动，即没有相同值，p正常移动
            if(left == right) p=p->next;
            // 如果left!=right，说明right有移动，left和right所指的都是相同值
            else p->next=right->next;
        }
        return myHead->next;
    }
};

1171. 从链表中删去总和值为零的连续节点（中等难度）

class Solution {
public:
    ListNode* removeZeroSumSublists(ListNode* head) {
        // 新建虚拟头结点
        ListNode* myHead=new ListNode(0);
        myHead->next=head;
        // 遍历
        ListNode*p=myHead;
        ListNode* left,* right;
        while(p->next!=nullptr){
            left=p->next;
            right=left;
            // 尝试移动right,记录left到right的和作为标准
            int sum=left->val;//[left,right]的元素之和，
            while(right->next){
                // 如果sum为零则退出需要删除节点
                if(sum==0)  break;
                // 如果sum不为零则继续累加直至表尾
                else{
                    right = right->next;//right前进
                    sum += right->val;//right
                }
            }
            if(sum!=0) p=p->next;// 如果sum不为零，p正常移动
            else p->next=right->next; // 如果sum为零，p移动到right的右侧
        }
        return myHead->next;
    }
};

二、反转链表的LeetCode题目

1、反转整个链表

206. 反转链表（简单难度）

剑指 Offer 24. 反转链表（简单难度）

剑指 Offer II 024. 反转链表（简单难度）

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* left=nullptr;
        ListNode* right=head;
        while(right!=nullptr){
            //保存
            ListNode* temp=right->next;
            //反转
            right->next=left;
            //更新
            left=right;
            right=temp;
        }
        return left;
    }
};

2、反转单链表的某个区间

92. 反转链表 II（中等难度）

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        // 新建虚拟头结点
        ListNode* myHead = new ListNode(0);
        myHead->next = head;
        // 慢指针先找到第left-1个节点
        ListNode* slow=myHead;
        int i=0;
        while(slow&&i<left-1){
            slow=slow->next;
            i++;
        }
        if(slow==nullptr) return myHead->next;//说明链表没有要反转的区间，直接返回
        // 慢指针和快指针一起反转[left,right]
        ListNode* rhead=slow->next;//第left个节点（反转序列的头结点）
        // 循环right-left次
        for(int i=left;i<right;i++){
            //保存
            ListNode* temp=rhead->next;//保存rhead的后1步
            rhead->next = temp->next;//rhead重新指向后2步
            //反转
            temp->next = slow->next;//rhead的后1步指向快指针
            //更新
            slow->next=temp;//慢指针指向rhead的后1步
        }
        // 更新头结点
        return myHead->next;
    }
};

3、判断是否是回文链表

234. 回文链表（简单难度）

剑指 Offer II 027. 回文链表（简单难度）

面试题 02.06. 回文链表（简单难度）

class Solution {
public:
    //反转链表
    ListNode* reverse(ListNode* head){
        ListNode* pre=NULL;
        ListNode* temp=NULL;
        ListNode* cur=head;
        while(cur){
            temp=cur->next;
            cur->next=pre;
            pre = cur;
            cur = temp;
        }
        head=pre;
        return head;
    }
    bool isPalindrome(ListNode* head) {
        // 特殊情况
        if (head == NULL || head->next == NULL) {
            return true;
        }
        ListNode* left=head;
        ListNode* right=head;
        //根据快慢指针找到中点，同时出发
        while(right->next&&right->next->next){
            right=right->next->next;//快指针走两步
            left=left->next;//慢指针走一步
        }
        //反转链表的后半部分
        right = reverse(left->next);//right指向后半部分头结点
        left  = head;//left指向前半部分头结点
        //比较链表的前后两部分
        while(right&&left){
            if(right->val!=left->val){
                return false;
            }
            right=right->next;
            left=left->next;
        }
        return true;
    }
};

三、两数相加的LeetCode题目

2. 两数相加（中等难度）

class Solution {
public:
    
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        // 新建结果链表的虚拟头结点
        ListNode* myHead = new ListNode(0);
        // 同时遍历2个可能不等长的链表
        ListNode* cur = myHead;//遍历指针
        int sum = 0;
        bool carry = false; 
        while(l1 != NULL || l2 != NULL){
            sum = 0;
            // 获取链表1的值
            if(l1 != NULL){
                sum += l1->val;
                l1 = l1 -> next;
            }
            // 获取链表2的值
            if(l2 != NULL){
                sum += l2->val;
                l2 = l2 -> next;
            }
            // 如果需要进位则+1
            if(carry) sum++;
            // 为结果链表添加新的元素
            cur -> next = new ListNode(sum % 10);//第一元素
            cur = cur -> next;
            carry = sum >= 10 ? true: false;//发现需要进位
        }
        //如果最后还需要+1位，则需要继续添加一个新结点
        if(carry) cur -> next = new ListNode(1);
        return myHead -> next;
    }
};

445. 两数相加 II（中等难度）

剑指 Offer II 025. 链表中的两数相加（中等难度）

面试题 02.05. 链表求和（中等难度）

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* slow=NULL;//慢指针
        ListNode* fast=head;//快指针
        while(fast!=NULL){
            //保存
            ListNode* temp = fast->next;
            //反转
            fast->next=slow;
            //更新
            slow=fast;
            fast=temp;
        }
        //更新头结点
        head=slow;
        return head;
    }
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* head=new ListNode(-1);//结果链表的虚拟头结点
        ListNode* cur=head;//遍历指针
        l1=reverseList(l1);
        l2=reverseList(l2);
        // 同时遍历2个链表
        int sum=0;
        bool carry=false;//是否需要进位
        while(l1||l2){
            sum=0;
            if(l1!=nullptr){
                sum+=l1->val;
                l1=l1->next;
            }
            if(l2!=nullptr){
                sum+=l2->val;
                l2=l2->next;
            }
            if(carry) sum++;
            // 为结果链表添加一个新的结果
            cur->next=new ListNode(sum%10);
            cur=cur->next;
            carry = sum >= 10 ? true: false;//发现需要进位
        }
        if(carry)   cur->next=new ListNode(1);
        head->next = reverseList(head->next);
        return head->next;
    }
};

附录

1、单链表的C++实现

#include<iostream>
using namespace std;

/*单链表的实现*/
class SingleList{
private:
    struct ListNode {
        int val;
        ListNode *next;
        ListNode() : val(0), next(nullptr) {}
        ListNode(int x) : val(x), next(nullptr) {}
        ListNode(int x, ListNode *next) : val(x), next(next) {}
    };
    ListNode * head;//头结点,头结点可以直接赋值，其他节点必须在上一个节点处添加
public:
    SingleList():head(nullptr){}
    /**增加**/
    void push_front(int value){
        ListNode* newNode= new ListNode(value);
        newNode->next=head;
        head=newNode;
    }
    void push_back(int value){
        ListNode * newNode=new ListNode(value);
        // 如果链表为空添加为头结点
        if(head==nullptr) {
            head=newNode;
            return;
        }
        // 如果链表不为空添加到链表末尾
        else{
            // 遍历找到链表的最后一个节点，注意不能是while(p),因为链表节点的添加必须在上一个节点操作
            ListNode *p=head;
            while(p->next){
                p=p->next;
            }
            p->next=newNode;
        }
    }
    void insert(int index,int value){
        if(index<0) return;
        if(index==0) push_front(value);
        //找到第index个元素
        int i=0;
        ListNode* p=head;
        while(p&&i<index){
            i++;
            p=p->next;
        }
        if(p==nullptr) return;
        //在第index元素后添加新元素
        ListNode* newNode=new ListNode(value);
        newNode->next=p->next;
        p->next=newNode;
    }
    /**删除**/
    void pop_front(){
        if(head!=nullptr){
            ListNode* del = head;
            head=head->next;
            delete del;
        }
    }
    void pop_back(){
        this->erase(this->size()-1);
    }
    // 删除第index个元素
    void erase(int index){
        if(index<0) return;
        if(index==0) pop_front();
        else{
            //尝试找到第index-1个元素,删除其p->next
            ListNode *p=head;
            int i=0;
            while (p&&i<index-1)
            {
                p=p->next;
                i++;
            }
            //没有找到，可能是index超出size
            if(p==nullptr)return;
            //如果找到了且p->next不为空
            if(p->next){
                ListNode * del=p->next;
                p->next=del->next; 
                delete del;
            }
        }

    }
    /**查找**/
    int front(){
        if(head!=nullptr) return head->val;
        return -1;
    }
    int get(int index){
        if(index<0) return -1;
        if(index==0) return front();
        // 遍历找到第index元素，访问其p->val
        int i=0;
        ListNode* p=head;
        while(p&&i<index){
            p=p->next;
            i++;
        } 
        // 如果没有找到
        if(p==nullptr) return -1;
        return p->val;
    }
    int back(){
        return this->get(this->size()-1);
    }
    int size(){
        int len=1;
        ListNode* p=head;
        if(p==nullptr) return 0;
        while(p->next){
            len++;
            p=p->next;
        }
        return len;
    }

    void show(string name=""){
        cout<<name;
        for(ListNode* p=head;p!=nullptr;p=p->next){
            cout<<p->val<<" ";
        }
        cout<<endl;
    }
};

int main()
{
    SingleList* lst=new SingleList();
    lst->push_back(1);
    lst->push_back(2);
    lst->push_back(3);
    lst->push_front(0);
    lst->insert(2,4);
    lst->show("插入后:");
    cout<<"get:"<<lst->get(1)<<endl;
    lst->pop_front();
    lst->erase(1);
    lst->pop_back();
    lst->pop_back();
    lst->pop_back();
    cout<<"len:"<<lst->size()<<endl;
    lst->show("删除后:");


    system("pause");
    return 0;
}

2、双链表的C++实现

#include<iostream>
using namespace std;

/*双链表的实现*/
class DoubleList{
private:
    struct ListNode {
        int val;
        ListNode *next,*prev;
        ListNode() : val(0), next(nullptr),prev(nullptr) {}
        ListNode(int x) : val(x), next(nullptr),prev(nullptr) {}
        ListNode(int x, ListNode *next,ListNode *prev) : val(x), next(next),prev(prev) {}
    };
    ListNode * head,*tail;//头结点指向链表第一个元素；尾结点指向最后一个元素
public:
    DoubleList():head(nullptr),tail(nullptr){}
    /**增加**/
    void push_front(int value){
        ListNode * newNode=new ListNode(value);
        if(head==nullptr){
            head=newNode;
            tail=head;
        }
        else{
            newNode->next=head;
            head->prev=newNode;
            head=newNode;
        }
    }
    void push_back(int value){
        ListNode * newNode=new ListNode(value);
        // 如果尾结点为空添加为尾结点和头结点
        if(tail==nullptr) {
            tail=newNode;
            head=tail;
            return;
        }
        // 如果尾结点不为空添加到尾结点尾部
        else{
            // 遍历找到链表的最后一个节点，注意不能是while(p),因为链表节点的添加必须在上一个节点操作
            newNode->prev=tail;
            tail->next=newNode;
            tail=newNode;
        }
    }
    // 插入第index个元素
    void insert(int index,int value){
        if(index<0) return;
        if(index==0) push_front(value);
        if(index==size()-1) push_back(value);
        // 找到第index个元素
        int i=0;
        ListNode* p=head;
        while(p&&i<index){
            i++;
            p=p->next;
        }
        if(p==nullptr) return;
        // 在index个元素后添加新元素
        ListNode* newNode=new ListNode(value);
        newNode->next=p->next;
        p->next->prev=newNode;
        newNode->prev=p;
        p->next=newNode;
    }
    /**删除**/
    void pop_front(){
        if(head!=nullptr){
            ListNode* del = head;
            head=head->next;
            if(head) head->prev=nullptr; // 如果链表存在2个以上元素
            else tail=nullptr;//如果链表只有一个元素
            delete del;
        }
    }
    void pop_back(){
        if(tail!=nullptr){
            ListNode * del= tail;
            tail=tail->prev;
            if(tail) tail->next=nullptr;
            else head=nullptr;
            delete del;
        }
        
    }
    // 删除第index个元素
    void erase(int index){
        if(index<0) return;
        if(index==0) pop_front();
        if(index==size()-1) pop_back();
        else{
            //尝试找到第index个元素,删除其p->next和p->prev
            ListNode *cur=head;
            int i=0;
            while (cur&&i<index)
            {
                cur=cur->next;
                i++;
            }
            //没有找到，可能是index超出size
            if(cur==nullptr)return;
            //如果找到了且p->next不为空
            ListNode * del=cur;
            ListNode *p=cur->prev;
            p->next=cur->next;
            if(cur->next){
                cur->next->prev=p;
            }
            delete del;
        }

    }
    /**查找**/
    int front(){
        if(head!=nullptr) return head->val;
        return -1;
    }
    int back(){
        if(tail!=nullptr) return tail->val;
        return -1;
    }
    int get(int index){
        if(index<0) return -1;
        if(index==0) return front();
        if(index==size()-1) return back();
        // 遍历找到第index元素，访问其p->val
        int i=0;
        ListNode* p=head;
        while(p&&i<index){
            p=p->next;
            i++;
        } 
        // 如果没有找到
        if(p==nullptr) return -1;
        return p->val;
    }
    
    int size(){
        int len=1;
        ListNode* p=head;
        if(p==nullptr) return 0;
        while(p->next){
            len++;
            p=p->next;
        }
        return len;
    }

    void show(string name=""){
        cout<<name;
        for(ListNode* p=head;p!=nullptr;p=p->next){
            cout<<p->val<<" ";
        }
        cout<<endl;
    }
};

int main()
{
    DoubleList* lst=new DoubleList();
    lst->push_back(1);
    lst->push_back(2);
    lst->push_back(3);
    lst->push_front(0);
    lst->insert(3,4);
    lst->show("插入后:");
    cout<<"get:"<<lst->get(2)<<endl;
    lst->pop_front();
    lst->erase(2);
    lst->pop_back();
    // lst->pop_back();
    // lst->pop_back();
    cout<<"len:"<<lst->size()<<endl;
    lst->show("删除后:");


    system("pause");
    return 0;
}