[CareerCup] Linked Lists―Q2.4 - c++编程基础

题目：

You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1’s digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.

EXAMPLE

Input: (3 -> 1 -> 5), (5 -> 9 -> 2)

Output: 8 -> 0 -> 8

翻译：

用单链表表示一个正整数，每个结点代表其中的一位数字，逆序排列，个位位于表头，最高位位于表尾，将两个数相加并返回结果，结果也由链表表示。
例如：

输入：(3 -> 1 -> 5)+(5 -> 9 -> 2)
输出：8 -> 0 -> 8

思路：

这道题目不难，也没有太大的技巧性，就按照最常规的思路来，只是要注意将所有的情况全部考虑到。

1、两个链表中有一个为NULL，这时直接返回另一个链表就行了；

2、如果两个链表都为空，这本身也包含在第1种情况中包；

3、如果两个链表长度不等，我们需要将二者相加后的结果保存在较长的链表上；

4、如果某位相加大于等于10，需要进位；

5、如果相加后的链表长度大于另两个链表中最长的那个链表的长度，则需要开辟新的节点，将其挂在长度较长的那个链表的表尾。

实现代码：

/**************************************************
题目描述：
用单链表表示一个正整数，每个结点代表其中的一位数字，
逆序排列，个位位于表头，最高位位于表尾，
将两个数相加并返回结果，结果也由链表表示。比如：
输入：(3 -> 1 -> 5)+(5 -> 9 -> 2)
输出：8 -> 0 -> 8
***************************************************/
#include
  
   
#include
   
     typedef struct Node { int data; struct Node *pNext; }NODE,*PNODE; PNODE create_list(); void traverse_list(PNODE); bool is_empty(PNODE); int length_list(PNODE); void clear_list(PNODE); PNODE addList(PNODE,PNODE); void AddShortToLong(PNODE,PNODE); int main() { printf(Create the first list: ); PNODE pHead1 = create_list(); printf(List 1: ); traverse_list(pHead1); fflush(stdin); //刷新输入缓冲区 printf(Create the second list: ); PNODE pHead2 = create_list(); printf(List 2: ); traverse_list(pHead2); PNODE pHead = addList(pHead1,pHead2); printf(After added,the new List: ); traverse_list(pHead); return 0; } /* 创建一个链表,并返回头指针 */ PNODE create_list() { int val; PNODE pHead =(PNODE)malloc(sizeof(NODE)); PNODE pCurrent = pHead; pCurrent->pNext = NULL; if(NULL == pHead) { printf(pHead malloc failed!); exit(-1); } printf(Input first data(q to quit):); while(scanf(%d,&val)==1) { PNODE pNew = (PNODE)malloc(sizeof(NODE)); if(NULL == pNew) { printf(pNew malloc failed!); exit(-1); } pNew->data = val; pCurrent->pNext = pNew; pNew->pNext = NULL; pCurrent = pNew; printf(Input next data(q to quit):); } return pHead; } /* 遍历链表 */ void traverse_list(PNODE pHead) { PNODE pCurrent = pHead->pNext; printf(now dataes in the list are: ); while(pCurrent != NULL) { printf(%d ,pCurrent->data); pCurrent = pCurrent->pNext; } printf( ); return ; } /* 判断链表是否为空 */ bool is_empty(PNODE pNode) { if(NULL == pNode->pNext) return true; else return false; } /* 求链表长度，即节点总数（不计入头节点） */ int length_list(PNODE pNode) { int count = 0; PNODE pCurrent = pNode->pNext; while(pCurrent != NULL) { count++; pCurrent = pCurrent->pNext; } return count; } /* 清空链表，即使链表只剩下头节点（头节点中没有数据） */ void clear_list(PNODE pHead) { PNODE p = pHead->pNext; PNODE r = NULL; while(p != NULL) { r = p->pNext; free(p); p = r; } pHead->pNext = NULL; return ; } /* 两个链表相加 */ PNODE addList(PNODE pHead1,PNODE pHead2) { if(!pHead1) return pHead2; if(!pHead2) return pHead1; int len1 = length_list(pHead1); int len2 = length_list(pHead2); if(len1 >= len2) { AddShortToLong(pHead1,pHead2); return pHead1; } else { AddShortToLong(pHead2,pHead1); return pHead2; } } /* 第一个链表的长度大于或等于第二个链表的长度， 将第二个链表加到第一个链表上 */ void AddShortToLong(PNODE pHeadLong,PNODE pHeadShort) { PNODE p1 = pHeadLong->pNext; PNODE p2 = pHeadShort->pNext; while(p1 && p2) { p1->data = p1->data + p2->data; if(p1->data >= 10) { p1->data -= 10; if(p1->pNext) { p1->pNext->data++; if(p1->pNext->data >= 10) //两链表长度不同，最后一位又有进位 { p1->pNext->data -= 10; PNODE pNew = (

[CareerCup] Linked Lists―Q2.4(一)