[CareerCup] Linked Lists—Q2.4

題目：

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 = (PNODE)malloc(sizeof(NODE));
						if(!pNew)
						{
							printf(malloc failed
);
							exit(-1);
						}
						pNew->pNext = NULL;
						pNew->data = 1;
						p1->pNext->pNext = pNew;
					}
				}
				else	//兩鏈表長度相同，且組後一位有進位
				{
					PNODE pNew = (PNODE)malloc(sizeof(NODE));
					if(!pNew)
					{
						printf(malloc failed
);
						exit(-1);
					}
					pNew->pNext = NULL;
					pNew->data = 1;
					p1->pNext = pNew;
				}
			}
			p1 = p1->pNext;
			p2 = p2->pNext;
		}
}

注：代碼開源到我的Github：https://github.com/mmc-maodun/CareerCup/tree/master