当前位置：
  1. 首页
  2. 拿捏算法面试
  3. 问题详情

【作业9】字节真题：单链表相加

对应课程链接：拿捏算法面试课程

字节真题：单链表相加

这道题还考过挺多次的，你们直接看图片的描述吧

image-20221024122407732

注意，不允许使用栈，队列等数据结构哦。

难点就是还得进位，而且链表只能前进不能后退。

思路：可以先它他们进行反转，相加之后，得到结果，再把结果进行反转

要求：
1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路。
2、给出你代码所用的时间复杂度和空间复杂度

核心模式做就行，这里我给一个统一的方法题

public ListNode linkedListAdd(ListNode head1, ListNode head2){

}

代码参考

// 注意，关于链表节点的定义（ListNode），我这里没有给出来哦
class SolutionAdd {
    // 反转链表
    public ListNode  reverseList(ListNode node){
        ListNode pre = null;
        ListNode q= null;
        while (node != null) {
            q= node.next;
            node.next = pre;
            pre = node;
            node = q;
        }
        return pre;
    }
    // 单链表相加
    public ListNode  addTwoNumbers(ListNode head1, ListNode head2) {
        // 虚拟头节点
        ListNode listNode = new ListNode(0);
        ListNode p = listNode;
        // sum 用来存放进位
        int sum = 0;
        while (head1 != null || head2 != null || sum!=0) {
            if (head1 != null) {
                sum += head1.val;
                head1 = head1.next;
            }

            if (head2 != null) {
                sum += head2.val;
                head2 = head2.next;
            }
            p.next = new ListNode(sum % 10);
            sum = sum / 10;
            p = p.next;
        }
        return listNode.next;
    }
}

时间复杂度：O(n+m)
空间复杂度：O(1)

shuaidi
146 5

共以下 5 个回答

  • 泡芙 永久会员 2023年9月15日 下午2:14
    • Time：O(N+M)
    • Space：O(1)
    public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        if (head1 == null || head2 == null) {
            return null;
        }

        // 将两个链表进行反转
        ListNode l1 = reverseList(head1);
        ListNode l2 = reverseList(head2);

        // 单链表相加
        // 定义一个新的链表来装相加的值
        ListNode res = new ListNode(0);
        ListNode tmp = res;
        // 是否需要进位
        int carry = 0;
        while (l1 != null || l2 != null) {
            int val = carry;
            if (l1 != null) {
                val += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                val += l2.val;
                l2 = l2.next;
            }
            carry = val / 10;
            tmp.next = new ListNode(val % 10);
            tmp = tmp.next;
        }

        // 如果 carry != 0，即需要进位，新增一个节点
        if (carry != 0) {
            tmp.next = new ListNode(carry);
        }

        // 把相加链表的值再反转
        return reverseList(res.next);
    }

    // 反转链表
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

    这道题与牛客网上的 链表相加(二)一样，觉得不好测试的同学可以在上面写，链接放在这里https://www.nowcoder.com/practice/c56f6c70fb3f4849bc56e33ff2a50b6b

    另外这道题是正向存放的，如果这道题是反向存放呢？题目链接也放在这里了，有兴趣的同学可以尝试一下 https://www.nowcoder.com/practice/521d83306d964c1188639033eb59621d?tpId=196&tqId=40273&ru=/exam/oj

    如果想在力扣上做，这里也有一道类似的：面试题 02.05. 链表求和，但是这道题是反向链表相加https://leetcode.cn/problems/sum-lists-lcci/

    0 赞同 0 条回复
  • 小肸 永久会员 2023年5月27日 下午9:52

    时间O(3(N+M))，空间O(2(N+M))。递归练习，有些耗空间。

        public static ListNode linkedListAdd(ListNode head1, ListNode head2){
        ListNode p1 = reserveList(head1);
        ListNode p2 = reserveList(head2);
        //记录进位
        int carry = 0;
        ListNode dummyHead = new ListNode(-1);
        ListNode cur = dummyHead;
        while (p1 != null && p2 != null) {
            int val = p1.val + p2.val + carry;
            if (val >= 10) {
                val %= 10;
                carry = 1;
            }
            cur.next = new ListNode(val);
            cur = cur.next;
            p1 = p1.next;
            p2 = p2.next;
        }
        ListNode nextNode = p1 == null ? p2 : p1;
        while (nextNode != null) {
            int val = nextNode.val + carry;
            if (val >= 10) {
                val %= 10;
                carry = 1;
            }
            cur.next = new ListNode(val);
            cur = cur.next;
            nextNode = nextNode.next;
        }
        if (carry == 1) {
            cur.next = new ListNode(1);
        }
        ListNode newHead = dummyHead.next;
        return reserveList(newHead);
    }
    public static ListNode reserveList(ListNode head) {
        if (head.next == null) {
            return head;
        }
        ListNode newHead = reserveList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
    0 赞同 0 条回复
  • 是梦终空 永久会员 2023年5月19日 下午5:19

    时间：O(n+m)
    空间：O(1)

    public class Main {
    public static void main(String[] args) {
        int[] arr = new int[]{9,9,9,9};
        ListNode l1 = create(arr);
        int[] arr1 = new int[]{9,9,9,9};
        ListNode l2 = create(arr1);
        int count = 0;
        ListNode l3 = linkedListAdd(l1, l2);
        l3 = reverse(l3);
        System.out.println(l3.toString());
    }

    public static ListNode linkedListAdd(ListNode head1, ListNode head2) {
        //先反转
        head1 = reverse(head1);
        head2 = reverse(head2);
        ListNode head = new ListNode(0);
        ListNode temp = head;
        boolean flag = false; //判断是否需要进位
        int x= 0;   //要进几位
        while (head1 != null || head2 != null) {
            int count = 0;          //链表的值
            if (flag) {             //如果需要进位 ,判断需要进几位
                count += x;
                flag = false;
                x = 0;
            }
            if (head1 != null) {
                count += head1.val;
                head1 = head1.next;
            }

            if (head2 != null) {
                count += head2.val;
                head2 = head2.next;
            }

            if (count > 10) {       //下次计算就需要进位了
                temp.next = new ListNode(count % 10);
                flag = true;
                x = count / 10;
            } else {
                temp.next = new ListNode(count);
            }
            temp = temp.next;
        }
        if(flag = true){
            temp.next = new ListNode(x);   
        }

        return head.next;
    }

    public static ListNode reverse(ListNode list) {
        ListNode pre = null;
        while (list != null) {
            ListNode temp = null;
            temp = list.next;
            list.next = pre;
            pre = list;
            list = temp;
        }
        return pre;
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

        @Override
        public String toString() {
            return "ListNode{" +
                    "val=" + val +
                    ", next=" + next +
                    '}';
        }
    }

    public static ListNode create(int[] arr) {
        ListNode head = new ListNode(0);
        ListNode temp = head;
        for (int i = 0; i < arr.length; i++) {
            temp.next = new ListNode(arr[i]);
            temp = temp.next;
        }
        return head.next;
    }
}
    0 赞同 0 条回复
  • 秊 永久会员 2023年5月17日 上午8:32

    时间：$O(n + m)$
    空间：$O(1)$

     public ListNode linkedListAdd(ListNode head1, ListNode head2) {
        // 第一次反转
        head1 = reverse(head1);
        head2 = reverse(head2);
        // 引入虚拟头节点
        ListNode header = new ListNode(-1);
        ListNode cur = header;
        int count = 0;

        while (head1 != null || head2 != null) {
            ListNode tmp = new ListNode(0);
            if (head1 != null) {
                tmp.val += head1.val;
                head1 = head1.next;
            }

            if (head2 != null) {
                tmp.val += head2.val;
                head2 = head2.next;
            } 

            // 更新 count
            tmp.val += count;
            count = tmp.val / 10;
            tmp.val %= 10;

            // 更新当前指针引用
            cur.next = tmp;
            cur = tmp;
        }

        // 判断整个结果链表的末尾，是否需要构造新的节点，根据当前进位的值判断
        if (count != 0) {
            cur.next = new ListNode(count);
        }

        // 第二次反转
        return reverse(header.next);
    }

    // 反转链表
    private ListNode reverse(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode pre = head;
        ListNode cur = head.next;
        pre.next = null;

        while (cur != null) {
            ListNode tmp = cur.next;
            cur.next = pre;

            pre = cur;
            cur = tmp;
        }

        return pre;
    }
    0 赞同 0 条回复
  • Everglow 永久会员 2023年5月8日 下午4:08

    时间O(n + m) 空间O(1)
    “java
    public class SolutionAdd {

    public static void main(String[] args) {
    ListNode head1 = create(new int[]{1, 2, 7, 9});
    ListNode head2 = create(new int[]{3, 4});
    ListNode listNode = linkedListAdd(head1, head2);
    print(listNode);
}

static class ListNode {
    int value;
    ListNode next;

    public ListNode(int value) {
        this.value = value;
    }
}

public static ListNode reverse(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode newHead = reverse(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}

public static ListNode linkedListAdd(ListNode head1, ListNode head2) {
    head1 = reverse(head1);
    head2 = reverse(head2);
    ListNode head = new ListNode(666);
    ListNode p = head;
    int sum = 0;
    while(head1 != null || head2 != null) {
        if(head1 != null) {
            sum += head1.value;
            head1 = head1.next;
        }
        if(head2 != null) {
            sum += head2.value;
            head2 = head2.next;
        }
        p.next = new ListNode(sum % 10);
        sum = sum / 10;
        p = p.next;
    }
    return reverse(head.next);
}

public static ListNode create(int[] value) {
    ListNode dummy = new ListNode(6666);
    ListNode p = dummy;
    for (int n : value) {
        p.next = new ListNode(n);
        p = p.next;
    }
    return dummy.next;
}

public static void print(ListNode head) {
    ListNode p = head;
    while (p != null) {
        System.out.print(p.value + " ");
        p = p.next;
    }
}

    }
    “

    0 赞同 0 条回复

# 回答此问题

后才能回答