2.25 链表 2 新建链表 82

2 Add Two Numbers

//新建链表
ListNode* dummy = new ListNode(0);
ListNode* ptr = dummy;
//增加结点
ptr->next = new ListNode(结点val);
ptr = ptr->next;
//返回结果
return dummy->next;复制

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        //l1 l2非负 链表 数是相反存储 每个结点只保存一个数 任务：相加 并将结果放在一个链表中作为结果
        //加法：从低位加到高位 并进行进位 需要从头到尾注意进位数
        //做循环：取数 做加法 取高位数保存 存个位数 指针向后移动
        //循环条件：两个链表指针 进位 有不为空
                
        ListNode* dummy = new ListNode(0);//哑节点
        ListNode* ptr = dummy;//指向新链表的指针
       
        int cf = 0; //指向新链表的指针
 
        while(l1 || l2 || cf){//只要有一个不为空或有进位 新链表构建就不能停
            int sum = cf;
            if(l1){
                sum += l1->val;
                l1 = l1->next;
            }
            if(l2){
                sum += l2->val;
                l2 = l2->next;
            }
            cf = sum/10;
            ptr->next = new ListNode(sum%10);//存个位数
            ptr = ptr->next;
 
        }
       
        return dummy->next;//返回真实头结点
    }
};复制

82 Remove Duplicates from Sorted List II

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
     //head是 排序链表 有重复的数字 仅包含一个数字的数 分离出来返回的链表也要排序 
     ListNode* dummy = new ListNode(0);
     ListNode* ptr = dummy;
     //使用指针temp 判断当下的val是否等于next的val如果相等 则往后走 并用哈希表记录当前值是有重复的
        //不能存入链表的情况：于下一个结点值==且为false !=且vec对应位为true
     ListNode* temp = head;
     unordered_map<int, bool> rep;
     if(temp == nullptr)
        return temp;
     while(temp->next != nullptr){
        int num1 = temp->val ,num2 = temp->next->val;
        //不管相不相等 且为true 不用管
        //相等且为false 置为true
        //不等且为false 加入新链表
        if(rep[num1] == 0){
            if(num1 == num2)
                rep[num1] = 1;
            else{
                ptr->next = new ListNode(num1);
                ptr = ptr->next;
            }
        }
        temp = temp->next;
     }
     //最后一个结点
     if(rep[temp->val] == 0){
        ptr->next = new ListNode(temp->val);
        ptr = ptr->next;
     }
     return dummy->next;
    }
};复制

优化：不使用哈希表&循环的优化

#include <u
nordered_map>
 
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head) return nullptr; // 处理空链表
 
        ListNode* dummy = new ListNode(0); // 哑结点，简化操作
        ListNode* ptr = dummy;
        ListNode* temp = head;
 
        std::unordered_map<int, bool> rep; // 记录数值是否重复
 
        while (temp) {
            bool isDuplicate = false;
            // 遍历完整的重复段
            while (temp->next && temp->val == temp->next->val) {
                isDuplicate = true;
                temp = temp->next; // 跳过重复节点
            }
 
            // 仅当 `temp->val` **从未重复**时才加入新链表
            if (!isDuplicate) {
                ptr->next = new ListNode(temp->val);
                ptr = ptr->next;
            }
 
            temp = temp->next; // 继续遍历
        }
 
        return dummy->next;
    }
};
 复制