当前位置：网站首页>＃yyds干货盘点＃面试必刷TOP101：链表相加(二)

＃yyds干货盘点＃面试必刷TOP101：链表相加(二)

2022-08-04 18:01:00 【51CTO】

1.简述：

描述

假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。

给定两个这种链表，请生成代表两个整数相加值的结果链表。

数据范围：，链表任意值要求：空间复杂度，时间复杂度

例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。

#yyds干货盘点# 面试必刷TOP101：链表相加(二)_数据_05

示例1

输入：

       
       [9,3,7],[6,3]
      
1.

返回值：

示例2

输入：

       
       [0],[6,3]
      
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;
       
    }
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.