头像

有点丶




离线:12小时前


最近来访(65)
用户头像
im0use
用户头像
QLW
用户头像
BK-201_3
用户头像
天才小笼包
用户头像
大地
用户头像
cc_xx
用户头像
牛马工厂
用户头像
苏苏_2
用户头像
.梅子酒.
用户头像
波波波波
用户头像
yxc
用户头像
昊子125
用户头像
用户头像
皮的小叮当
用户头像
Kanam
用户头像
不成大神不改名
用户头像
CCSU_JP
用户头像
runrunrun
用户头像
摘樱桃
用户头像
1234_6


有点丶
11天前

1.从尾到头打印链表
输入一个链表的头结点,按照 从尾到头 的顺序返回节点的值。

返回的结果用数组存储。

数据范围
0≤ 链表长度 ≤1000。

样例
输入:[2, 3, 5]
返回:[5, 3, 2]


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> printListReversingly(ListNode* head) {
        vector<int> a;
        while(head!=NULL)
        {
            a.push_back(head->val);
            head=head->next;
        }
        reverse(a.begin(),a.end());
        return a;
    }
};

2.在O(1)时间删除链表结点,删除指定节点
给定单向链表的一个节点指针,定义一个函数在O(1)时间删除该结点。

假设链表一定存在,并且该节点一定不是尾节点。

数据范围
链表长度 [1,500]。

样例
输入:链表 1->4->6->8
删掉节点:第2个节点即6(头节点为第0个节点)

输出:新链表 1->4->8

/**
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        ListNode* newNode=new ListNode(-1);
        newNode=node->next;
        node->val=newNode->val;
        node->next=newNode->next;

    }
};

3.反转链表
定义一个函数,输入一个链表的头结点,反转该链表并输出反转后链表的头结点。

思考题:

请同时实现迭代版本和递归版本。
数据范围
链表长度 [0,30]。

样例
输入:1->2->3->4->5->NULL

输出:5->4->3->2->1->NULL

迭代法:
空间复杂度分析:遍历时只有3个额外变量,所以额外的空间复杂度是 O(1)。
时间复杂度分析:只遍历一次链表,时间复杂度是 O(n)。
代码

/**
 * 
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode*cur=head;
        ListNode*pre=NULL;
        while(cur)
        {
            ListNode*ne=cur->next;
            cur->next=pre;
            pre=cur;
            cur=ne;
        }
        return pre;

    }
};

递归法:
首先我们先考虑 reverseList 函数能做什么,它可以翻转一个链表,并返回新链表的头节点,也就是原链表的尾节点。
所以我们可以先递归处理 reverseList(head->next),这样我们可以将以head->next为头节点的链表翻转,并得到原链表的尾节点tail,此时head->next是新链表的尾节点,我们令它的next指针指向head,并将head->next指向空即可将整个链表翻转,且新链表的头节点是tail。
空间复杂度分析:总共递归 n 层,系统栈的空间复杂度是 O(n),所以总共需要额外 O(n)的空间。
时间复杂度分析:链表中每个节点只被遍历一次,所以时间复杂度是 O(n)。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode*tail = reverseList(head->next);
        head->next->next=head;
        head->next=NULL;
        return tail;

    }
};

4.反转链表中的某一段

5.合并两个排序的链表
输入两个递增排序的链表,合并这两个链表并使新链表中的结点仍然是按照递增排序的。

数据范围
链表长度 [0,500]。

样例
输入:1->3->5 , 2->4->5

输出:1->2->3->4->5->5

时间复杂度
两个链表各遍历一次,所以时间复杂度为O(n)
代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode*dummy = new ListNode(0);
        ListNode*cur=dummy;

        while(l1!=NULL&l2!=NULL)
        {
            if(l1->val<l2->val)
            {
                cur->next=l1;
                l1=l1->next;
            }
            else
            {
                cur->next=l2;
                l2=l2->next;
            }
            cur=cur->next;
        }
        if(l1!=NULL)
        {
            cur->next=l1;
        }
        else
        {
            cur->next=l2;
        }
        return dummy->next;
    }
};

6.删除排序链表中的重复元素(I)
给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。
输入:head = [1,1,2]
输出:[1,2]
输入:head = [1,1,2,3,3]
输出:[1,2,3]

时间复杂度
循环了一次链表,时间复杂度为O(n)
代码:

/**
 * 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) {
       ListNode*duyy = head;
        while(duyy!=NULL)
        {
            if(duyy->next!=NULL&&duyy->val==duyy->next->val)
            {
                duyy->next=duyy->next->next;
            }
            else
            {
                duyy=duyy->next;
            }
        }
        return head;
    }
};

7.删除排序链表中的重复元素(II)
在一个排序的链表中,存在重复的节点,请删除该链表中重复的节点,重复的节点不保留。

数据范围
链表中节点 val 值取值范围 [0,100]。
链表长度 [0,100]。

样例1
输入:1->2->3->3->4->4->5

输出:1->2->5
样例2
输入:1->1->1->2->3

输出:2->3

算法
(线性扫描)
之前做的删除节点的题是有重复元素只保留1个下来,这道题的要求是一个都不保留。(有点狠兄弟)
那么就要求在cur指针还没扫到重复元素区间的第一个元素的时候,就知道它们是重复元素了。
那么针对于2,解决方法是新建一个指针go,go = cur->next。就像cur相当于是上帝视角,是大佬,go是小兵向前冲。一般第一步cur->next->val是一定等于go->val的,接下来是继续判断,如果有重复元素,小兵go会继续向前冲,最后碰到不同元素,跳出while循环。
逻辑是这样:如果cur的后面是有一段相同元素,cur是不会涉足这段元素的,go会遍历这一段的每一个元素。最后,cur是相同元素区间的前一个节点,go是相同元素区间的后一个节点。
接下来的if判断,if(cur->next->next == go)成立意味着cur和go之间没有重复元素,那么cur向前走一步。如果else成立,说明有重复元素,那么cur->next指向go,直接略过相同元素这一段,相当于删除了这一段。
时间复杂度
O(n)

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplication(ListNode* head) {
        ListNode*dummy = new ListNode(-1);
        dummy->next=head;
        ListNode*cur=dummy;
        while(cur->next)
        {
            ListNode*go=cur->next;
            while(go&&cur->next->val==go->val)go=go->next;
            if(cur->next->next==go)cur=cur->next;
            else cur->next=go;
        }

        return dummy->next;
    }

};

8.链表中倒数第k个节点
输入一个链表,输出该链表中倒数第 k 个结点。

注意:

k >= 1;
如果 k 大于链表长度,则返回 NULL;
数据范围
链表长度 [0,30]。

样例
输入:链表:1->2->3->4->5 ,k=2

输出:4

时间复杂度:
1.先将链表反转,循环链表一次
2.后有循环一次链表查找第k位
时间复杂度为O(n)

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* findKthToTail(ListNode* pListHead, int k) {
        ListNode*pre=NULL;
        ListNode*cur=pListHead;

        while(cur)
        {
            ListNode*ne=cur->next;
            cur->next=pre;
            pre=cur;
            cur=ne;
        }
        int i=1;

        while(pre&&i<k)
        {
            pre=pre->next;
            i++;
        }
        return pre;
    }
};

9.两个链表的第一个公共结点
输入两个链表,找出它们的第一个公共结点。

当不存在公共节点时,返回空节点。

数据范围
链表长度 [1,2000]。

样例
给出两个链表如下所示:
A:
····· a1 → a2
····· · ······ ↘
····················· c1 → c2 → c3
··················· · ↗
······ b1 → b2 → b3
B:

输出第一个公共节点c1

时间复杂度
循环链表 o(n)

注意:
没有公共节点,也会同时走到对方的NULL而相等的
为什么我运行if(p -> next)会错呢?
因为要考虑二者没有相交的情况,这个时候返回要让两个指针都指向尾部的null,要是写成(p->next)会发现自始至终指针没有指向尾部的NULL

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
        ListNode* p=headA;
        ListNode* q=headB;

        while(p!=q)
        {
            if(p)
            {
                p=p->next;
            }
            else
            {
                p=headB;
            }
            if(q)
            {
                q=q->next;
            }
            else
            {
                q=headA;
            }
        }
        return q;
    }
};

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* curA = headA;
        ListNode* curB = headB;
        int lenA = 0, lenB = 0;
        while (curA != NULL) { // 求链表A的长度
            lenA++;
            curA = curA->next;
        }
        while (curB != NULL) { // 求链表B的长度
            lenB++;
            curB = curB->next;
        }
        curA = headA;
        curB = headB;
        // 让curA为最长链表的头,lenA为其长度
        if (lenB > lenA) {
            swap (lenA, lenB);
            swap (curA, curB);
        }
        // 求长度差
        int gap = lenA - lenB;
        // 让curA和curB在同一起点上(末尾位置对齐)
        while (gap--) {
            curA = curA->next;
        }
        // 遍历curA 和 curB,遇到相同则直接返回
        while (curA != NULL) {
            if (curA == curB) {
                return curA;
            }
            curA = curA->next;
            curB = curB->next;
        }
        return NULL;
    }
};

10.设计链表
设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性:val 和 next。val 是当前节点的值,next 是指向下一个节点的指针/引用。如果要使用双向链表,则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

在链表类中实现这些功能:

get(index):获取链表中第 index 个节点的值。如果索引无效,则返回-1。
addAtHead(val):在链表的第一个元素之前添加一个值为 val 的节点。插入后,新节点将成为链表的第一个节点。
addAtTail(val):将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val):在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度,则该节点将附加到链表的末尾。如果 index 大于链表长度,则不会插入节点。如果index小于0,则在头部插入节点。
deleteAtIndex(index):如果索引 index 有效,则删除链表中的第 index 个节点。

示例:

MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2); //链表变为1-> 2-> 3
linkedList.get(1); //返回2
linkedList.deleteAtIndex(1); //现在链表是1-> 3
linkedList.get(1); //返回3

提示:

所有val值都在 [1, 1000] 之内。
操作次数将在  [1, 1000] 之内。
请不要使用内置的 LinkedList 库。

代码

class MyLinkedList {
public:
    struct ListNode
    {
        int val;
        ListNode*next;
        ListNode(int val):val(val),next(NULL){}
    };
    // 初始化链表
    MyLinkedList() {
        _dummyHead = new ListNode(0); // 这里定义的头结点 是一个虚拟头结点,而不是真正的链表头结点
        _size = 0;
    }
    // index=0;是头节点(第一个节点)
    int get(int index) {
        if(index>_size-1||index<0)
        {
            return -1;
        }
        ListNode*p = _dummyHead->next;
        while(index--)
        {
            p=p->next;
        }
        return p->val;
    }

    void addAtHead(int val) {
        ListNode*node = new ListNode(val);
        node->next=_dummyHead->next;
        _dummyHead->next=node;
        _size++;
    }

    void addAtTail(int val) {
        ListNode*node= new ListNode(val);
        ListNode*cur=_dummyHead;
        while(cur->next)
        {
            cur=cur->next;
        }
        cur->next=node;
        _size++;
    }

    void addAtIndex(int index, int val) {
        ListNode*node=new ListNode(val);
        if(index>_size)return;
        ListNode*cur=_dummyHead;
        while(index--)
        {
             cur=cur->next;
        }
        node->next=cur->next;
        cur->next=node;
        _size++;
    }

    void deleteAtIndex(int index) {
        if(index>=0&&index<_size)
        {
            ListNode*cur=_dummyHead;
            while(index--)
            {
                cur=cur->next;
            }
            ListNode* tmp = cur->next;
            cur->next = cur->next->next;//若只单纯留这一句,这多余的节点还在内存中没删除,消耗多余内存
            delete tmp;                 
            _size--;
        }
    }
      // 打印链表
    void printLinkedList() {
        ListNode* cur = _dummyHead;
        while (cur->next != nullptr) {
            cout << cur->next->val << " ";
            cur = cur->next;
        }
        cout << endl;
    }
    private:
    int _size;
    ListNode* _dummyHead;
};  

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

11.链表中环的入口结点
给定一个链表,若其中包含环,则输出环的入口节点。

若其中不包含环,则输出null。

数据范围
节点 val 值取值范围 [1,1000]。
链表长度 [0,500]。

样例
QQ截图20181202023846.png

给定如上所示的链表:
[1, 2, 3, 4, 5, 6]
2
注意,这里的2表示编号是2的节点,节点编号从0开始。所以编号是2的节点就是val等于3的节点。

则输出环的入口节点3.
QQ图片20220701210025.png
QQ图片20220701210918.png
时间复杂度

算其指针走的次数,O(n)
slow总共走了2x+y步,fast总共走了2x+2y+x步(理想情况),所以两个指针总共走了 5x+3y 步
由于当第一次slow走到b点时,fast最多追一圈即可追上slow,所以y小于环的长度,所以 x+y 小于等于链表总长度。
代码:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *entryNodeOfLoop(ListNode *head) {
        ListNode*slow=head;
        ListNode*fast=head;
        while(fast&&fast->next)
        {
            slow=slow->next;
            fast=fast->next->next;
            if(slow==fast)
            {
                slow=head;
                while(slow!=fast)
                {
                    slow=slow->next;
                    fast=fast->next;
                }
                return fast;
            }
        }
        return NULL;
    }
};

//判断是否有环:
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode*fast=head;
        ListNode*slow=head;
        while(fast&&fast->next)
        {
            slow=slow->next;
            fast=fast->next->next;
            if(slow==fast)
            {
                return true;
            }
        }
        return false;
    }
};

12.两两交换链表中的节点
给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。
示例 1:
输入:head = [1,2,3,4]
输出:[2,1,4,3]
示例 2:
输入:head = []
输出:[]
QQ图片20220701214324.png
时间复杂度:
O(n),其中 n是链表的节点数量。需要对每个节点进行更新指针的操作。
代码

/**
 * 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* swapPairs(ListNode* head) {
        ListNode*dummy=new ListNode(0);
        dummy->next=head;
        ListNode*cur = dummy;
        while(cur->next&&cur->next->next)
        {
            ListNode*tmp1=cur->next;
            ListNode*tmp2=cur->next->next->next;

            cur->next=cur->next->next;
            cur->next->next=tmp1;
            cur->next->next->next=tmp2;

            cur=cur->next->next;
        }
        return dummy->next;
    }
};

13 移除链表元素
给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点
输入:head = [1,2,6,3,4,5,6], val = 6
输出:[1,2,3,4,5]
示例 2:
示例 1:
输入:head = [], val = 1
输出:[]
示例 3:

输入:head = [7,7,7,7], val = 7
输出:[]

时间复杂度:
循环查询一遍链表,O(n)

代码

/**
 * 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* removeElements(ListNode* head, int val) {
        ListNode*dummy=new ListNode(-1);
        dummy->next=head;
        ListNode*cur = dummy;
        while(cur->next)
        {
            if(cur->next->val==val)
            {
                cur->next=cur->next->next;
            }
            else
            {
                cur=cur->next;
            }

        }
        return dummy->next;
    }
};

14.删除链表的倒数第N个节点
给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
输入:head = [1,2,3,4,5], n = 2
输出:[1,2,3,5]
示例 2:

输入:head = [1], n = 1
输出:[]
示例 3:

输入:head = [1,2], n = 1
输出:[1]

提示:

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

时间复杂度
O(n)
双指针的经典应用,如果要删除倒数第n个节点,让fast移动n步,然后让fast和slow同时移动,直到fast指向链表末尾。删掉slow所指向的节点就可以了。
代码:

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode*dummy = new ListNode(-1);
        dummy->next=head;
        ListNode*slow=dummy;
        ListNode*fast=dummy;

        while(n--)
        {
            fast=fast->next;
        }
        while(fast->next)
        {
            fast=fast->next;
            slow=slow->next;
        }
        ListNode*tmp=slow->next;
        slow->next=tmp->next;
        delete tmp;
        return dummy->next;

    }
};

15.链表中倒数第k个节点
输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。

例如,一个链表有 6 个节点,从头节点开始,它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例:

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

时间复杂度:
O(n)

若带有虚拟头节点,多半遍历时while循环内时判断是否有next
不带有 则可以直接判断该节点
代码


class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode*slow=head;
        ListNode*fast=head;

        while(k--)
        {
            fast=fast->next;
        }
        while(fast)         //为什么这里变为fast->next就不可以呢,因为若只有三个元素,k=3,此时k已经变成了null,如何判断null的下一//个,所以出现错误,不行,但使用虚拟节点开头就可以,因为始终多一个点,k不能超过链表的节点(不包括虚拟节//点的数量)
        {
            slow=slow->next;
            fast=fast->next;
        }
        return slow;
        //  ListNode*dummy = new ListNode(-1);
        // dummy->next=head;
        // ListNode*slow=dummy;
        // ListNode*fast=dummy;

        // while(k--)
        // {
        //     fast=fast->next;
        // }
        // while(fast->next)
        // {
        //     fast=fast->next;
        //     slow=slow->next;
        // }
        // return slow->next;
    }
};

16.链表求和
给定两个用链表表示的整数,每个节点包含一个数位。

这些数位是反向存放的,也就是个位排在链表首部。

编写函数对这两个整数求和,并用链表形式返回结果。
输入:(7 -> 1 -> 6) + (5 -> 9 -> 2),即617 + 295
输出:2 -> 1 -> 9,即912
时间复杂度:
循环两个链表,O(max(n,m))
代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
         ListNode*dummy1=new ListNode(-1);
         ListNode*dummy2=new ListNode(-1);
         ListNode*dummy3=new ListNode(-1);
         dummy1->next=l1;
         dummy2->next=l2;

         ListNode*cur1=dummy1;
         ListNode*cur2=dummy2;
         ListNode*cur3=dummy3;

         int t=0;
         while(cur1->next!=NULL||cur2->next!=NULL||t)
         {
             if(cur1->next)t+=cur1->next->val;
             if(cur2->next)t+=cur2->next->val;
             ListNode*node=new ListNode(t%10);
             t=t/10;
             cur3->next=node;
             cur3=cur3->next;
             //细节
             if(cur1->next)
             {
                cur1=cur1->next;
             }
             if(cur2->next)
             {
                cur2=cur2->next;
             }
         }
         return dummy3->next;
    }
};

17.链表求和II
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外,这两个数字都不会以零开头。
输入:l1 = [7,2,4,3], l2 = [5,6,4]
输出:[7,8,0,7]

输入:l1 = [2,4,3], l2 = [5,6,4]
输出:[8,0,7]

时间复杂度:O(max(m,n))
其中 m 和 n** 分别为两个链表的长度。我们需要遍历两个链表的全部位置,而处理每个位置只需要 O(1) 的时间。

空间复杂度:O(m + n),其中 mm 和 nn 分别为两个链表的长度。空间复杂度主要取决于我们把链表内容放入栈中所用的空间。

无需反转链表,利用栈实现逆序处理数据
代码

/**
 * 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) {
            stack<int> cur1,cur2;
            ListNode*dummy=new ListNode(-1);
            while(l1)
            {
                cur1.push(l1->val);
                l1=l1->next;
            }
            while(l2)
            {
                cur2.push(l2->val);
                l2=l2->next;
            }

            int t=0;
            ListNode*head=new ListNode(-1);
            while(!cur1.empty()||!cur2.empty()||t)
            {
                if(!cur1.empty())t+=cur1.top();
                if(!cur2.empty())t+=cur2.top();              
                ListNode*node =new ListNode(t%10); 
                t/=10;
                if(!cur1.empty())cur1.pop();
                if(!cur2.empty())cur2.pop();
                // cur->next=node;
                // cur=cur->next;  这样拿到的链表还需反转才能得到正确答案,因为是倒着存的, 因此要倒着输出
                node->next=dummy->next; //头插法,即反转了一遍
                dummy->next=node;
            }
            return dummy->next;
    }
};

18.合并两个链表
给你两个链表 list1 和 list2 ,它们包含的元素分别为 n 个和 m 个。

请你将 list1 中下标从 a 到 b 的全部节点都删除,并将list2 接在被删除节点的位置。

输入:list1 = [0,1,2,3,4,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
输出:[0,1,2,1000000,1000001,1000002,5]
解释:我们删除 list1 中下标为 3 和 4 的两个节点,并将 list2 接在该位置。上图中蓝色的边和节点为答案链表。

输入:list1 = [0,1,2,3,4,5,6], a = 2, b = 5, list2 = [1000000,1000001,1000002,1000003,1000004]
输出:[0,1,1000000,1000001,1000002,1000003,1000004,6]

时间复杂度
O(n)
代码

class Solution {
public:
    ListNode* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) {
        ListNode*dummy=new ListNode(-1);
        dummy->next=list1;
        ListNode*cur=dummy;

        for(int i=0;i<a;i++)
        {
            cur=cur->next;
        }
        // 此时cur指向a索引节点的前驱节点

        for(int i=a;i<=b;i++)
        {
            cur->next=cur->next->next;
        }
        ListNode*dummy1=new ListNode(-1);
        dummy1->next=list2;
        ListNode*ne=dummy1;
        while(ne->next)
        {
            ne=ne->next;
        }
        ne->next=cur->next;
        cur->next=dummy1->next;
        return dummy->next;
    }
};

19.交换链表中的节点
给你链表的头节点 head 和一个整数 k 。

交换 链表正数第 k 个节点和倒数第 k 个节点的值后,返回链表的头节点(链表 从 1 开始索引)。

输入:head = [1,2,3,4,5], k = 2
输出:[1,4,3,2,5]

输入:head = [7,9,6,6,7,8,3,0,9,5], k = 5
输出:[7,9,6,6,8,7,3,0,9,5]

双指针,交换值即可
代码

/**
 * 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* swapNodes(ListNode* head, int k) {
        ListNode*dummy=new ListNode(-1);
        dummy->next=head;
        ListNode*fast=dummy;
        ListNode*slow=dummy;
        ListNode*change=dummy;
        for(int i=0;i<k;i++)
        {
            change=change->next;
            fast=fast->next;
        }
        while(fast->next)
        {
            slow=slow->next;
            fast=fast->next;
        }
        slow=slow->next;
        swap(slow->val,change->val);
        return dummy->next;
    }
};


活动打卡代码 AcWing 1866. 围栏刷漆

有点丶
2个月前
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>

using namespace std;

const int N = 110;
int q[N];

int main()
{
    int a,b,c,d;
    cin>>a>>b>>c>>d;

    for(int i=a;i<b;i++)
    {
        q[i]++;
    }
    for(int i=c;i<d;i++)
    {
        q[i]++;
    }
    int sum=0;
    for(int i=0;i<=N;i++)
    {
        if(q[i]!=0)
        {
            sum++;
        }

    }
    cout<<sum;
    return 0;
}


活动打卡代码 AcWing 1775. 丢失的牛

有点丶
2个月前
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int x, y; cin>>x>>y;
    int ans=0, dist=1, d=1;
    //dist: 距离
    //d: 方向(1向右 -1向左)
    while(1)
    {
        if((d==1 && x<=y && y<=x+dist) || (d==-1 && y<=x && x<=y+dist))
        {
            //找到了Bessie
            ans+=abs(y-x);
            cout<<ans;
            break;
        }
        //没有找到Bessie
        else dist*=2, ans+=dist, d*=-1;
    }
    return 0;
}



活动打卡代码 AcWing 1460. 我在哪?

有点丶
2个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 1471. 牛奶工厂

有点丶
2个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 1684. 大型植被恢复

有点丶
2个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 1696. 困牛排序

有点丶
2个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 1715. 桶列表

有点丶
2个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 1726. 挤奶顺序

有点丶
2个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 3347. 菊花链

有点丶
2个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~