NC40 链表相加(二)(c++)
2022/3/11 12:15:02
本文主要是介绍NC40 链表相加(二)(c++),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
方法一:反转链表
所以我们的入手则是对链表进行对齐,我们都是从后面开始对齐与计算的,所以很容易想到反转链表后进行相加。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: /** * * @param head1 ListNode类 * @param head2 ListNode类 * @return ListNode类 */ ListNode* addInList(ListNode* head1, ListNode* head2) { // write code here if(head1 == nullptr){ return head2; } if(head2 == nullptr){ return head1; } head1 = reverseList(head1);//反转链表 head2 = reverseList(head2); ListNode* head = nullptr;//保存结果 int carry = 0;//进位 int sum = 0; while(head1 || head2 || carry){ sum = carry; if(head1){ sum += head1->val; head1 = head1 -> next; } if(head2){ sum +=head2->val; head2 = head2 -> next; } ListNode* pnext = new ListNode(sum % 10); //把node插入到头结点 pnext->next = head; head = pnext; // head = head -> next = pnext; //正序插入,需要逆转结果 carry = sum / 10; } return head; } ListNode* reverseList(ListNode* head){ if(head == nullptr){ return head; } ListNode* cur = nullptr; while(head){ ListNode* temp = head -> next; head->next = cur; cur = head; head = temp; } return cur; } };
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: /** * * @param head1 ListNode类 * @param head2 ListNode类 * @return ListNode类 */ ListNode* addInList(ListNode* head1, ListNode* head2) { // write code here if(head1 == nullptr){ return head2; } if(head2 == nullptr){ return head1; } stack<ListNode*>stk1; stack<ListNode*>stk2; //把head1,head2节点存入stack中 ListNode*p1 = head1; ListNode*p2 = head2; while(p1){ stk1.push(p1); p1 = p1 -> next; } while(p2){ stk2.push(p2); p2 = p2 -> next; } ListNode* head = nullptr;//保存结果 int carry = 0;//进位 int sum = 0; while(!stk1.empty() || !stk2.empty() || carry){ sum = carry; if(!stk1.empty()){//加上栈顶元素 sum += stk1.top()->val; stk1.pop(); } if(!stk2.empty()){ sum += stk2.top()->val; stk2.pop(); } ListNode* pnext = new ListNode(sum % 10); //把node插入到头结点 pnext->next = head; head = pnext; // head = head -> next = pnext; carry = sum / 10; } return head; } };
这篇关于NC40 链表相加(二)(c++)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享
- 2024-06-28忘记eyoucms后台密码怎么办?-icode9专业技术文章分享
- 2024-06-26终极指南:Scrum中如何设置需求优先级
- 2024-06-26AI大模型企业应用实战(25)-为Langchain Agent添加记忆功能
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding
- 2024-06-23AI大模型企业应用实战(15)-langchain核心组件
- 2024-06-23AI大模型企业应用实战(16)-langchain核心组件
- 2024-06-23AI 大模型企业应用实战(06)-初识LangChain