原文

 

Question:

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Input:   (2 ->  4  ->  3) + (5 -> 6  ->  4)
Output: 7  ->​​​​​​​ ​​​​​​​ 0  ->​​​​​​​ ​​​​​​​ 8

 


翻譯

 

問題:

      給定兩個非空的鍊結串列,分別代表兩個非負整數串列,串列內每個元素皆由反方向儲存(越前面的節點位數越低),每一個節點代表一個位元。

將此兩個鍊結串列相加並回傳

 

解答:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *newNode(int data)
{
    struct ListNode *NewNode = (struct ListNode *) malloc(sizeof(struct ListNode));
    NewNode->val = data;
    NewNode->next = NULL;
    return NewNode;
}
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    
    struct ListNode *head    = NULL;
    struct ListNode *current = NULL;
    struct ListNode *rear    = NULL;
    int temp    = 0 , result = 0;
    
    while (l1 != NULL || l2 != NULL)
    {
        // 計算總合
        result = temp + (l1? l1->val: 0) + (l2? l2->val: 0);
        
        // 進位處理
        temp   = (result >= 10)? 1 : 0;
        result = (result >= 10)? (result-10):result;
        
        // 節點串連
        current = newNode(result);
        if (!head)
            head = current;
        else
            rear-> next = current;

        rear = current;
        
        //指標後移 
        if (l1) 
            l1 = l1->next;
        if (l2) 
            l2 = l2->next;    

        //最後的進位處理   
        if (temp == 1)
            rear->next = newNode(1);
    }
    return head;
}

解析:

      此題為難度中級,需具備linklist基本概念與細心的進位處理。

需要注意的是: 

1. 基本功能 如: new node (新增節點),最好可獨立出另一個function,增加程式的可讀性

2. 可多善加使用 如: bigger number = (5>3)?5:3; 的技巧來簡化程式

文章標籤
創作者介紹
創作者 C 的頭像
C

DummyH的部落格

C 發表在 痞客邦 留言(0) 人氣()