This question has also been used as a classic interview question by Micosoft, Amazon, Bloomberg, Airbnb and Adobe

I believe those of you who read this title are familiar with this question, which is the second question in Leecode. The reason why I have to write it separately is mainly for me. There is a knowledge point that is more important and there are several tips.

The title

Give two non-empty linked lists to represent two non-negative integers. Their respective bits are stored in reverse order, and each node can store only one digit. If we add these two numbers together, a new linked list is returned to represent their sum. You can assume that neither of these numbers will start with 0, except for the number 0.

Example:

Input :(2 -> 4 -> 3) + (5 -> 6 -> 4)

Output: 7 -> 0 -> 8

Reason: 342 + 465 = 807

class ListNode { int val; ListNode next; ListNode(int x) { val = x; }}Copy the code

Generally speaking, it is to get the node value from two non-empty lists and do an addition to generate a new list. Put forward some questions based on the examples:

① How to determine the first node?

② If we determine that the head node is 7, how do we keep the previous node 7 when we move to the next node?

DummyHead virtual head node:

For a singly linked list, the only thing that keeps it connected is its head node, so for example 7 is our head node, but we don’t know what the head node is until we count the head node 7. Here we have a general approach: create a dummyHead. We start with a head node of 0, and after evaluating the list, we just need to get dummyHead. Next, which is the list we want.

  ListNode dummyHead = new ListNode(0);
Copy the code

Pointer node:

To solve the second problem, when the head nodes 2 and 5 of the two linked lists are obtained, it can be calculated that the head node of dummyHead points to 7, but we need to move dummyHead = dummyHead. Next to the next node, then the value of 4 and 6 of the two linked lists can be calculated and assigned to dummyHead. In this case, dummyHead’s head node 7 will be removed, so we need a pointer node curr to point to dummyHead. When curr moves, dummyHead always keeps the node.

Reference code

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummyHead = new ListNode(0); ListNode p = l1, q = l2, curr = dummyHead; Int carry = 0; // carry while (p! = null || q ! = null) { int x = (p ! = null) ? p.val : 0; int y = (q ! = null) ? q.val : 0; int sum = carry + x + y; carry = sum / 10; curr.next = new ListNode(sum % 10); // curr = curr.next; // if (p ! = null) p = p.next; If (q! = null) q = q.next; } if (carry > 0) { curr.next = new ListNode(carry); } return dummyhead.next; }Copy the code

Test cases:

@Test
public void isAddTwoNumbers() {
    ListNode l1 = new ListNode(2);
    l1.next = new ListNode(4);
    l1.next.next = new ListNode(3);
    ListNode l2 = new ListNode(5);
    l2.next = new ListNode(6);
    l2.next.next = new ListNode(4);
    ListNode listNode = addTwoNumbers(l1, l2);
    Assert.assertNotNull(listNode.val);
}
Copy the code

Popular recommendation: **

Epoll and Java Nio

ThreadPoolExecutor ThreadPool

Swastika parsing: Recently, the service is ready to go live, adding JVM parameters to the microservice

Wanwen long word analysis: want to enter big factory, you have to master the CPU cache foundation

At the end of this article, I recently compiled an interview material “Java Interview Process Manual”, covering Java core technology, JVM, Java concurrency, SSM, microservices, databases, data structures and so on.

How to get it: Follow the Nuggets, call me anytime, more content coming.