【LeetCode】1171. 从链表中删去总和值为零的连续节点、面试题 02.05. 链表求和

绝地灬酷狼 2024-03-25 10:03 8阅读 0赞

>  作者：小卢
> 
> 专栏：《Leetcode》
> 
> 喜欢的话：世间因为少年的挺身而出，而更加瑰丽。 ——《人民日报》
> 
> ![7d63d497b5114103b3dd7633a1ba4731.jpeg][]
> 
> --------------------
> 
> **目录**
> 
>  1171. 从链表中删去总和值为零的连续节点
> 
>  面试题 02.05. 链表求和
> 
> --------------------

## 1171. 从链表中删去总和值为零的连续节点 ##

[1171. 从链表中删去总和值为零的连续节点][1171.]

题目描述：

给你一个链表的头节点 head，请你编写代码，反复删去链表中由 总和 值为 0 的连续节点组成的序列，直到不存在这样的序列为止。

删除完毕后，请你返回最终结果链表的头节点。

你可以返回任何满足题目要求的答案。

（注意，下面示例中的所有序列，都是对 ListNode 对象序列化的表示。）

示例：

![5eb37c52bf414e84bacdce6b06264212.png][]

代码：

struct ListNode* removeZeroSumSublists(struct ListNode* head){
        struct ListNode*newhead=(struct ListNode*)malloc(sizeof(struct ListNode));
        newhead->next=head;
        struct ListNode*cur1=newhead;
        struct ListNode*cur2=head;
        while(cur1)
        {
            int num=0;
            cur2=cur1->next;
            while(cur2)
            {
                num-=cur2->val;
                if(num==0)
                {
                    cur1->next=cur2->next;
                }
                cur2=cur2->next;
            }
            cur1=cur1->next;
        }
        return newhead->next;
    }

## 面试题 02.05. 链表求和 ##

[面试题 02.05. 链表求和][02.05.]

题目描述：

给定两个用链表表示的整数，每个节点包含一个数位。

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

编写函数对这两个整数求和，并用链表形式返回结果。

示例：

![e5dd6d4dbb274fa6b5f2c345b7b76883.png][]

思路：

暴力解法是不可以的，两个链表相加的值会大于10的18次方，大于longlong的数据范围

我们可以每位相加，然后计入它的进位值，放到一个新的链表中。

代码：

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
        struct ListNode*cur1=l1;
        struct ListNode*cur2=l2;
        struct ListNode*newhead=NULL;
        struct ListNode*tail=NULL;
        int carry=0;//进位值
        while(cur1||cur2)
        {
            int num1=0;
            int num2=0;
            if(cur1)
            num1=cur1->val;
            if(cur2)
            num2=cur2->val;
            int sum=num1+num2+carry;
            //创建一个新的链表
            if(newhead)
            {
                tail->next=(struct ListNode*)malloc(sizeof(struct ListNode));
                tail=tail->next;
                tail->val=sum%10;
                tail->next=NULL;
            }
            else
            {
                newhead=tail=(struct ListNode*)malloc(sizeof(struct ListNode));
                tail->val=sum%10;
                tail->next=NULL;
            }
            carry=sum/10;
            if(cur1)
            cur1=cur1->next;
            if(cur2)
            cur2=cur2->next;
        }
        if(carry>0)//最高位可能大于0，比如：10000000
        {
             tail->next=(struct ListNode*)malloc(sizeof(struct ListNode));
             tail=tail->next;
             tail->val=carry;
             tail->next=NULL;
        }
        return newhead;
    }

[7d63d497b5114103b3dd7633a1ba4731.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/4ba4f7803b054358bbc0a71ac2327bb5.png
[1171.]: https://leetcode.cn/problems/remove-zero-sum-consecutive-nodes-from-linked-list/
[5eb37c52bf414e84bacdce6b06264212.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/663cab1375fb451a8fa211b93bb1ce9c.png
[02.05.]: https://leetcode.cn/problems/sum-lists-lcci/
[e5dd6d4dbb274fa6b5f2c345b7b76883.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/6fd1cee208f144c0bbdbc7b367c2eaff.png