首页 > 代码库 > 两个链表相加
两个链表相加
1 题目
You are giventwo linked lists representing two non-negative numbers. The digits are storedin reverse order
and each of their nodes contain a single digit. Add the twonumbers and return it as a linked list.
Input: (2 -> 4 -> 3)+ (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
2 分析
该题目属于链表的相加，需要注意的有：
(1) 考虑两个链表的长度，尤其是链表为空时也能处理。
(2) 每个结点只表示一位数字。
(3) 当链表末尾结点相加后若有进位，则需要申请新的结点存储信息。
3 核心代码：
int listLength(ListNode* head) //递归得到链表的长度{ return head ? 1 + listLength(head ->next) : 0; } ListNode *addTwoNumbers(ListNode *l1, ListNode *l2){ //把两个链表相加(前面的参数为长链表) if (listLength(l1) < listLength(l2)){ return addTwoNumbers(l2, l1); } ListNode *head1 = l1, *head2 = l2; int inc = 0; bool isEnd = false; while (head2){ int val = head1 -> val + head2-> val + inc; head1 -> val = val % 10; inc = val / 10; if (head1 -> next){ head1 = head1 -> next; }else{ isEnd = true; } head2 = head2 -> next; } while (inc){ //当短链表计算完之后 int val = isEnd ? inc : head1 ->val + inc; if (isEnd){ head1 -> next = new ListNode(val % 10); }else{ head1 -> val = val % 10; } inc = val / 10; if (head1 -> next){ head1 = head1 -> next; }else{ isEnd = true; } } return l1; }
4 以下为代码的完整实现
#include "stdafx.h"#include<string.h>#include<iostream>using namespace std;struct ListNode { //sizeof(ListNode):8 int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; int listLength(ListNode* head) //递归得到链表的长度{ return head ? 1 + listLength(head ->next) : 0; } ListNode *addTwoNumbers(ListNode *l1, ListNode *l2){ //把两个链表相加(前面的参数为长链表) if (listLength(l1) < listLength(l2)){ return addTwoNumbers(l2, l1); } ListNode *head1 = l1, *head2 = l2; int inc = 0; bool isEnd = false; while (head2){ int val = head1 -> val + head2-> val + inc; head1 -> val = val % 10; inc = val / 10; if (head1 -> next){ head1 = head1 -> next; }else{ isEnd = true; } head2 = head2 -> next; } while (inc){ //当短链表计算完之后 int val = isEnd ? inc : head1 ->val + inc; if (isEnd){ head1 -> next = new ListNode(val % 10); }else{ head1 -> val = val % 10; } inc = val / 10; if (head1 -> next){ head1 = head1 -> next; }else{ isEnd = true; } } return l1; }//******************************************************************ListNode *createList(int arr[],int len){ //根据数组创建链表 ListNode* head = NULL,*p; p=head; for(int i=0; i<len; i++){ if(i==0){ head = new ListNode(arr[i]); p = head; }else{ p->next = new ListNode(arr[i]); p = p->next; } } return head;}void printList(ListNode *head){ //输出链表 ListNode *p = head; if(head==NULL) cout<<"空链表"<<endl; else{ while(p){ cout<<p->val<<" "; p = p->next; } cout<<endl; }}int main(int argc, char * argv[]){ //32位系统中所有指针(包括复杂结构体)均为4个字节，float、long和int类型为4个字节，char为1个字节，double为8个字节 //char arr[] = "12345678"; //strlen:8 sizeof:9 sizeof(arr)/sizeof(arr[0]):9 //作为参数时 strlen:8 sizeof:4 sizeof(arr)/sizeof(arr[0]):4 //int arr[] = {1,2,3,4,5,6,7,8}; //strlen:x sizeof:32 sizeof(arr)/sizeof(arr[0]):8 //作为参数时 strlen:x sizeof:4 sizeof(arr)/sizeof(arr[0]):1 int arr1[] = {2, 4, 3}; //表示从低位到高位 int arr2[] = {5, 6, 4}; int len1 = sizeof(arr1)/sizeof(arr1[0]); int len2 = sizeof(arr2)/sizeof(arr2[0]); ListNode *l1 = createList(arr1,len1); ListNode *l2 = createList(arr2,len2); printList(addTwoNumbers(l1,l2)); system("pause"); return 0;}
两个链表相加
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。