❝

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 begins with a “0”, except for the number “0”

❞

Example:

Input :(2 -> 4 -> 3) + (5 -> 6 -> 4)Output: 7 -> 0 -> 8Reason: 342 + 465 = 807Copy the code

Answer:

❝

The number of digits in the linked list is stored in reverse order. In fact, this makes it easier, because when the operation of addition happens, the digit is added from the ones digit, while the operation of the linked list starts from the lowest digit, which exactly conforms to the operation order of addition (take the data given in the question as an example).

❞


Since it is a sum, it is not difficult to know that, take out each node in the two linked lists and sum (sum). If the sum is greater than 10, a carry 1 is recorded. Then, take sum to mod 10, and the result is the first effective node of the target linked list.

Implementation process:

1. The core method is to iterate over two linked lists and sum them up node by node

  • Since we do not know the number of nodes in the list that requires the sum (i.e. the number of loops), we choose the while loop. As long as any of the linked list nodes are not null, the loop needs to continue
  • However, since there are carry cases, it is not possible to stop the loop when the carry is not 0 (such as 9999+1).

Create a new linked list to store the summation results

  • For linked list problems, it is common to create a flag node that holds no specific value and whose next is responsible for pointing to the first valid node (always pointing to the first, not moving), mainly for the convenience of returning to the resulting target list
  • At the same time, it needs to create a current node, which is responsible for generating each node. It is mobile, and every node generated, it needs to move one node back, thus realizing the construction of a new linked list

The language expression ability is a little poor, the description may not be very clear, there are necessary annotations in the code, I hope it can help to understand

Code implementation

class ListNode
{
    public $val = 0;
    public $next = null;
    public function __construct($val)
 {  $this->val = $val;  } }  class LeetCode002 { / * * * @param ListNode $l1  * @param ListNode $l2  * @return ListNode * / public function addTwoNumbers($l1.$l2)  {  if ($l1 == null && $l2 == null) {  return null;  }   $tag= new ListNode(0); // Create an empty node $current = $tag;  $addOne= 0; / / carry while ($l1! = null ||$l2! = null ||$addOne! = 0) { $val1 = $l1== null ? Zero:$l1->val;  $val2 = $l2== null ? Zero:$l2->val;  $sum = $val1 + $val2 + $addOne;  $current->next = new ListNode($sum % 10);  $current = $current->next;  $addOne = intval($sum/ 10); // Strongly typed languages do not have this problem if ($l1! = null) { $l1 = $l1->next;  }  if ($l2! = null) { $l2 = $l2->next;  }  }  return $tag->next;  } }  //Test Case $leetCode = new LeetCode002(); $l1 = new ListNode(2); $l1->next = new ListNode(4);   $l2 = new ListNode(5); $l2->next = new ListNode(6);  $newList = $leetCode->addTwoNumbers($l1.$l2); $str = ' '; while ($newList! = null) { $str. =$newList->val.'- >';  $newList = $newList->next; }  echo $str; Copy the code

The execution result