C語言實現兩數相加2018-09-23
/*給定兩個非空連結串列來表示兩個非負整數。位數按照逆序方式儲存,它們的每個節點只儲存單個數字。將兩數相加返回一個新的連結串列。
你可以假設除了數字 0 之外,這兩個數字都不會以零開頭。
示例:
輸入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出:7 -> 0 -> 8
原因:342 + 465 = 807*/
/**
* Definition for singly-linked list.
* struct ListNode {
*int val;
*struct ListNode *next;
* };
*/
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2)
{
struct ListNode *p = NULL, *q = NULL, *head = NULL;
int index = 0, x, y, sum = 0;
while (l1 != NULL || l2 != NULL)
{
x = (l1 != NULL) ? l1->val : 0;/*當l1非空時x等於l1所指向的值*/
y = (l2 != NULL) ? l2->val : 0;/*當l2非空時y等於l2所指向的值*/
sum = x + y + index;/*求和的時候記得加上用來進位的index*/
p = (struct ListNode*)malloc(sizeof(struct ListNode));
if (p != NULL)/*當節點分配成功*/
{
p->val = sum % 10;/*對和求餘數*/
index = sum / 10;/*計算是否需要進位*/
p->next = NULL;
}
if (q == NULL)/*才產生了一個節點的時候,讓head指向該節點*/
{
q = p;
head = q;
}
else
{
q->next = p;/*將每一個節點連線起來*/
q = p;
}
/*判斷l1是否已經指向了一個空節點,這一步很重要, 也很危險,切記不能寫成if(l1->next!NULL)這樣會產生死迴圈(l1和l2一直指向最後一個節點)*/
if (l1)
l1 = l1->next;
if (l2)
l2 = l2->next;
}
if (index == 1)/*當最後一個節點相加超過10了,需要再產生一個節點來完成進位*/
{
p = (struct ListNode*)malloc(sizeof(struct ListNode));
if (p != NULL)
{
p->val = 1;
p->next = NULL;
q->next = p;
q = p;
}
}
return head;
}
/*心得:
*1、寫過程略微複雜一點的程式一定要寫好虛擬碼,然後在寫的過程中再轉化為標準C語言;
*2、對於指標的使用,在指標改變指向,即移動或者交換的時候一定要留心,當指標移動的時候出現麻煩,可以往後思考一步到兩步,就可以發現其問題;
*3、對於相似問題的求解,一定要學會歸納一個模型,即使用幾行程式碼就可以實現一系列相似問題的求解。
*/