牛客在线编程101-11链表相加(二)

我就是我 2023-10-04 19:41 55阅读 0赞

题目  
假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。  
给定两个这种链表，请生成代表两个整数相加值的结果链表。  
数据范围：0 \\le n,m \\le 10000000≤n,m≤1000000，链表任意值 0 \\le val \\le 90≤val≤9  
要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)

例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。  
解析：  
链表翻转相加再翻转

import java.util.*;
    
    /*
     * public class ListNode {
     *   int val;
     *   ListNode next = null;
     * }
     */
    
    public class Solution {
        
        /**
         * 
         * @param head1 ListNode类 
         * @param head2 ListNode类 
         * @return ListNode类
         */ 
        public ListNode addInList (ListNode head1, ListNode head2) {
        
            // write code here
            //翻转链表
            ListNode p1 = reverseList(head1);
            ListNode p2 = reverseList(head2);
            //新链表存储结果
            ListNode fake = new ListNode(-1);
            ListNode cur = fake;
    
            int tmp = 0;//进位
            while(p1 != null || p2 != null || tmp != 0) {
        
                int val1 = p1 == null ? 0 : p1.val;
                int val2 = p2 == null ? 0 : p2.val;
                cur.next = new ListNode((val1 + val2 + tmp) % 10);
                tmp = (val1 + val2 + tmp) / 10;
                cur = cur.next;
                p1 = p1 == null ? null : p1.next;
                p2 = p2 == null ? null : p2.next;
            }
            //把结果翻转
            return reverseList(fake.next);
            
        }
    
        public ListNode reverseList(ListNode head) {
        
             ListNode pre = null;
             ListNode cur = head;
             ListNode next = null;
             while(cur != null) {
        
                next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
             }
             return pre;
        }
    }