牛客每日刷题之链表

作者简介：我是18shou，一名即将秋招的java实习生

个人主页：_18shou

系列专栏：牛客刷题专栏

推荐一款模拟面试、刷题神器 在线刷题面经模拟面试

目录

题目

思路

 题解

复杂度

结语

题目

链表相加(二)
假设链表中每一个节点的值都在0-9之间， 那么链表整体就可以代表一个整数。
给定两个这种链表，请生成代表两个整数相加值的结果链表。
数据范围:0≤n,m<1000000,链表任意值0<val<9
要求:空间复杂度0(n),时间复杂度0(n)
例如:链表1为9->3->7,链表2为6->3,最后生成新的结果链表为1->0->0->0.

思路

假设链表中每一个节 点的值都在0-9之间，那么链表整体就可以代表一个整数。
我们知道题目已经限定了每个节点的值都不为负数了，所以我们就可以不考虑符号的问题了，那么就很简单了。
我们先看- - :下题目给的例子: .
例如:链表1为9->3->7,链表2为6->3,最后生成新的结果链表为1->0->0->0.
从这个例子我们可以得到:
1、两个链表的长度可能不等，需要对齐
2、相加后可能需要进位
对齐进位
因为我们无法保证两个链表长度一致， 所以我们干脆从后往前对齐，跟我们整数再做加法一样
 

 题解

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) {
        // 进行判空处理
        if(head1 == null)
            return head2;
        if(head2 == null){
            return head1;
        }
        // 反转h1链表
        head1 = reverse(head1);
        // 反转h2链表
        head2 = reverse(head2);
        // 创建新的链表头节点
        ListNode head = new ListNode(-1);
        ListNode nHead = head;
        // 记录进位的数值
        int tmp = 0;
        while(head1 != null || head2 != null){
            // val用来累加此时的数值（加数+加数+上一位的进位=当前总的数值）
            int val = tmp;
            // 当节点不为空的时候，则需要加上当前节点的值
            if (head1 != null) {
                val += head1.val;
                head1 = head1.next;
            }
            // 当节点不为空的时候，则需要加上当前节点的值
            if (head2 != null) {
                val += head2.val;
                head2 = head2.next;
            }
            // 求出进位
            tmp = val/10;
            // 进位后剩下的数值即为当前节点的数值
            nHead.next = new ListNode(val%10);
            // 下一个节点
            nHead = nHead.next;

        }
        // 最后当两条链表都加完的时候，进位不为0的时候，则需要再加上这个进位
        if(tmp > 0){
            nHead.next = new ListNode(tmp);
        }
        // 重新反转回来返回
        return reverse(head.next);
    }

    // 反转链表
    ListNode reverse(ListNode head){
        if(head == null)
            return head;
        ListNode cur = head;
        ListNode node = null;
        while(cur != null){
            ListNode tail = cur.next;
            cur.next = node;
            node = cur;
            cur = tail;
        }
        return node;
    }
}

复杂度

空间复杂度O(n),时间复杂度0(n)

结语

兄弟们，一起来刷题嘎嘎的写题