链表相加(一)

struct ListNode* ListAdd(struct ListNode* l1, struct ListNode* l2 ) {
    if(l1==NULL)return l2;
    struct ListNode*p=l1,*q=l2,*pre=l1;
    int temp=0;
    while(p&&q)
    {
        int now=p->val+q->val+temp;
        p->val=now%10;
        temp=now/10;
        pre=p;
        p=p->next;
        q=q->next;
    }
    if(q){
        pre->next=q;
        p=pre->next;
    }
    while(p)
    {
        int now=p->val+temp;
        p->val=now%10;
        temp=now/10;
        pre=p;
        p=p->next;
    }
    if(temp)
    {
        struct ListNode* jinwei=(struct ListNode*)malloc(sizeof(struct ListNode));
        jinwei->val=temp;
        pre->next=jinwei;
        jinwei->next=NULL;
    }
    return l1;
}

/**
 *  #[derive(PartialEq, Eq, Debug, Clone)]
 *  pub struct ListNode {
 *      pub val: i32,
 *      pub next: Option<Box<ListNode>>
 *  }
 * 
 *  impl ListNode {
 *      #[inline]
 *      fn new(val: i32) -> Self {
 *          ListNode {
 *              val: val,
 *              next: None,
 *          }
 *      }
 *  }
 */
struct Solution{

}

impl Solution {
    fn new() -> Self {
        Solution{}
    }

    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    *
    * 
        * @param l1 ListNode类 
        * @param l2 ListNode类 
        * @return ListNode类
    */
    pub fn ListAdd(&self, l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        // write code here
        let mut result_dummy_head = Some(Box::new(ListNode::new(233)));
        let mut r_p = &mut result_dummy_head;
        let mut n1_p = &l1;
        let mut n2_p = &l2;
        let mut carry = 0;
        while n1_p.is_some() && n2_p.is_some() {
            let mut result_val = n1_p.as_ref().unwrap().val + n2_p.as_ref().unwrap().val + carry;
            
            carry = result_val / 10;
            result_val %= 10;
            r_p.as_mut().unwrap().next = Some(Box::new(ListNode::new(result_val)));
            r_p= &mut r_p.as_mut().unwrap().next;
            n1_p=&n1_p.as_ref().unwrap().next;
            n2_p=&n2_p.as_ref().unwrap().next;
        }
        while n1_p.is_some() {
            let mut result_val = n1_p.as_ref().unwrap().val  + carry;
            
            carry = result_val / 10;
            result_val %= 10;
            r_p.as_mut().unwrap().next = Some(Box::new(ListNode::new(result_val)));
            r_p= &mut r_p.as_mut().unwrap().next;
            n1_p=&n1_p.as_ref().unwrap().next;
        }
        while n2_p.is_some() {
            let mut result_val =  n2_p.as_ref().unwrap().val + carry;
            
            carry = result_val / 10;
            result_val %= 10;
            r_p.as_mut().unwrap().next = Some(Box::new(ListNode::new(result_val)));
            r_p= &mut r_p.as_mut().unwrap().next;
            n2_p=&n2_p.as_ref().unwrap().next;
        }
        if carry != 0 {
            r_p.as_mut().unwrap().next = Some(Box::new(ListNode::new(carry)));
            r_p= &mut r_p.as_mut().unwrap().next;
        }
        result_dummy_head.unwrap().next
    }
}

# -*- coding: utf-8 -*-


class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class LinkedList:
    def __init__(self):
        self.head = None

    def initLinkedList(self, nums):
        n = len(nums)

        if n > 0:
            self.head = ListNode(nums[0])
            cur = self.head
            for i in range(1, n):
                cur.next = ListNode(nums[i])
                cur = cur.next

        return self.head

    @staticmethod
    def printLinkedList(head):
        if not head:
            return []

        cur, res = head, []
        while cur:
            res.append(cur.val)
            cur = cur.next
        return res

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param l1 ListNode类
# @param l2 ListNode类
# @return ListNode类
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/521d83306d964c1188639033eb59621d?tpId=196&tqId=40273&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D7%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=
    算法：
        从前往后，遍历链表l1和l2，对于第i项相加和sum = h1.val + h2.val + carry，新建节点ListNode(sum % 10), 记录进位carry = sum / 10
    复杂度：
        时间复杂度：O(min(M, N) ~ max(M, N))
        空间复杂度：O(1)
    """

    def ListAdd(self, l1, l2):
        # write code here
        if not l1:
            return l2
        elif not l2:
            return l1

        head1, head2, carry = l1, l2, 0
        dummy = ListNode(-1)
        cur = dummy

        while head1 and head2:
            sum = head1.val + head2.val + carry
            cur.next = ListNode(sum % 10)
            carry = sum / 10
            head1 = head1.next
            head2 = head2.next
            cur = cur.next

        while head1:
            if carry == 0:
                cur.next = head1
                break
            sum = carry + head1.val
            cur.next = ListNode(sum % 10)
            carry = sum / 10
            head1 = head1.next
            cur = cur.next

        while head2:
            if carry == 0:
                cur.next = head2
                break
            sum = carry + head2.val
            cur.next = ListNode(sum % 10)
            carry = sum / 10
            head2 = head2.next
            cur = cur.next

        if carry: # 链表遍历结束，仍有进位，如1 + 9
            cur.next = ListNode(carry)

        return dummy.next


if __name__ == "__main__":
    sol = Solution()

    # nums1, nums2 = [2, 5, 6], [5, 6, 1]

    # nums1, nums2 = [0], [1, 2, 3, 4, 5, 6]

    nums1, nums2 = [9, 9, 9], [9, 9, 0]

    # nums1, nums2 = [7, 5, 3, 5, 6, 2, 9, 1], [2, 7, 0, 9, 3, 6]

    # nums1, nums2 = [9, 9, 9, 9, 9, 9, 9, 9], [9, 9, 9, 9, 9, 9]

    l = LinkedList()
    l1, l2 = l.initLinkedList(nums1), l.initLinkedList(nums2)
    # print LinkedList.printLinkedList(l1), LinkedList.printLinkedList(l2)

    res = sol.ListAdd(l1, l2)
    print l.printLinkedList(res)



# python2直接超时 无语的效率

ListNode res = new ListNode(-1);
        ListNode cur = res;
        int carry = 0;
        while(head1 != null || head2 != null || carry != 0){
            int i = head1 == null ? 0 : head1.val;
            int j = head2 == null ? 0 : head2.val;
            int sum = i + j + carry;
            
            carry = sum / 10;
            ListNode tem = new ListNode(sum % 10);
            
            cur.next = tem;
            cur = cur.next;
            head1 = head1 == null ? null : head1.next;
            head2 = head2 == null ? null : head2.next;
            
        }        
        return res.next;