BM11. [两个链表生成相加链表]

https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295

BM11. 两个链表生成相加链表

https://www.nowcoder.com/practice/c56f6c70fb3f4849bc56e33ff2a50b6b?tpId=295&sfm=github&channel=nowcoder

题目分析

这个题目就是翻转链表外加一个进位符号就可以搞定，另外取模和取整 / and %感受一下即可，主要考察的还是我们的细心程度
可以看图说话

步骤分析

手写一个翻转链表函数，对于我们来说基本上是没有任何的难度的事情

    public ListNode reverse(ListNode head) {
    if (head == null || head.next == null)
        return head;
    ListNode pre = null;
    ListNode cur = head;
    while (cur != null) {
        ListNode next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
    }

关键设置进位符号flag，另外新开一个链表用来存储结果，由于链表存储的和我们要处理的数字顺序是逆序，我们可以先翻转两个链表

int flag = 0;
ListNode dummy = new ListNode(-1);
ListNode newHead = dummy;
head1 = reverse(head1);
head2 = reverse(head2);

第一个循环判断head1和head2同时不空的情况，获取当前位的值，以及进位值，拼接到新链表，然后指针后移

while(head1 != null && head2 != null){
            int val = (head1.val + head2.val + flag) % 10;
            flag = (head1.val + head2.val + flag) / 10;
            ListNode tmp = new ListNode(val);
            newHead.next = tmp;
            newHead = newHead.next;
            head1 = head1.next;
            head2 = head2.next;
        }

处理head1还是不为null的情况，其实可以复用上面的代码，就是head2已经空了直接将head2的相关信息删除即可；同理当head2还是不为null的情况和head1的处理方式基本上又是一致的。

while(head1 != null){
            int val = (head1.val + flag) % 10;
            flag = (head1.val + flag) / 10;
            ListNode tmp = new ListNode(val);
            newHead.next = tmp;
            newHead = newHead.next;
            head1 = head1.next;
        }
        while(head2 != null){
            int val = (head2.val + flag) % 10;
            flag = (head2.val + flag) / 10;
            ListNode tmp = new ListNode(val);
            newHead.next = tmp;
            newHead = newHead.next;
            head2 = head2.next;
        }

最后有一个点非常的重要那就是，都完成了还有关注进位，如果还有进位那么就需要将进位也放到链表中，比如 9 + 1 = 10，同时因为我们翻转了链表为了个位的方向和我们遍历的方向一致，那么我们就需将结果也翻转回去。

if(flag > 0){
            ListNode tmp = new ListNode(flag);
            newHead.next = tmp;
        }

完整题解

 public ListNode addInList (ListNode head1, ListNode head2) {
        int flag = 0;
        ListNode dummy = new ListNode(-1);
        ListNode newHead = dummy;
        head1 = reverse(head1);
        head2 = reverse(head2);
        while(head1 != null && head2 != null){
            int val = (head1.val + head2.val + flag) % 10;
            flag = (head1.val + head2.val + flag) / 10;
            ListNode tmp = new ListNode(val);
            newHead.next = tmp;
            newHead = newHead.next;
            head1 = head1.next;
            head2 = head2.next;
        }
        while(head1 != null){
            int val = (head1.val + flag) % 10;
            flag = (head1.val + flag) / 10;
            ListNode tmp = new ListNode(val);
            newHead.next = tmp;
            newHead = newHead.next;
            head1 = head1.next;
        }
        while(head2 != null){
            int val = (head2.val + flag) % 10;
            flag = (head2.val + flag) / 10;
            ListNode tmp = new ListNode(val);
            newHead.next = tmp;
            newHead = newHead.next;
            head2 = head2.next;
        }
        if(flag > 0){
            ListNode tmp = new ListNode(flag);
            newHead.next = tmp;
        }
        return reverse(dummy.next);
    }


    public ListNode reverse(ListNode head){
        if(head == null || head.next == null)
            return head;
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

复杂度分析

• 时间复杂度：，为链表1的长度,为链表2的长度
• 空间复杂度：，没有使用新的额外空间