題目信息

源地址：兩數(shù)相加

給你兩個?非空?的鏈表，表示兩個非負(fù)的整數(shù)。它們每位數(shù)字都是按照?逆序?的方式存儲的，并且每個節(jié)點只能存儲?一位?數(shù)字。

請你將兩個數(shù)相加，并以相同形式返回一個表示和的鏈表。

你可以假設(shè)除了數(shù)字 0 之外，這兩個數(shù)都不會以 0 開頭。

提示信息

示例 1

	輸入：l1 = [2,4,3], l2 = [5,6,4]
	輸出：[7,0,8]
	解釋：342 + 465 = 807

示例 2

	輸入：l1 = [0], l2 = [0]
	輸出：[0]

示例 3

	輸入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
	輸出：[8,9,9,9,0,0,0,1]

提示

• 每個鏈表中的節(jié)點數(shù)在范圍?[1, 100]?內(nèi)
• 0 <= Node.val <= 9
• 題目數(shù)據(jù)保證列表表示的數(shù)字不含前導(dǎo)零

實現(xiàn)邏輯

結(jié)點累加

這道題目將兩個鏈表結(jié)合成一個鏈表，比較清晰的思路就是，類似于四則運(yùn)算中的加法，從個位往高位進(jìn)行每一位相加，如果當(dāng)前位的結(jié)果大于等于 10 時則需要在高位加 1。

解析到程序當(dāng)中，既可以使用循環(huán)的方式，也可以使用遞歸的思維。循環(huán)的方式是將兩個鏈表同步遞增，而遞歸的方式是每次計算完一位時再對鏈表的下一個結(jié)點做遞歸處理。

通過循環(huán)的方式解決這個問題，時間復(fù)雜度是?O(n)，空間復(fù)雜度也是?O(n)，這里的 n 指的是最長的那個鏈表節(jié)點數(shù)。

	package cn.fatedeity.algorithm.leetcode;
	public class AddTwoNumbers {
	public ListNode answer(ListNode l1, ListNode l2) {
	ListNode result = new ListNode();
	ListNode listNode = result;
	boolean addOne = false;
	while (l1 != null || l2 != null || addOne) {
	int sum = 0;
	if (l1 != null) {
	sum += l1.val;
	l1 = l1.next;
	}
	if (l2 != null) {
	sum += l2.val;
	l2 = l2.next;
	}
	if (addOne) {
	sum += 1;
	}
	addOne = sum >= 10;
	listNode.next = new ListNode(sum % 10);
	listNode = listNode.next;
	}
	return result.next;
	}
	}
	class ListNode {
	int val;
	ListNode next;
	ListNode() {
	}
	ListNode(int val) {
	this.val = val;
	}
	ListNode(int val, ListNode next) {
	this.val = val;
	this.next = next;
	}
	}

題目信息

源地址：兩數(shù)相加

給你兩個?非空?的鏈表，表示兩個非負(fù)的整數(shù)。它們每位數(shù)字都是按照?逆序?的方式存儲的，并且每個節(jié)點只能存儲?一位?數(shù)字。

請你將兩個數(shù)相加，并以相同形式返回一個表示和的鏈表。

你可以假設(shè)除了數(shù)字 0 之外，這兩個數(shù)都不會以 0 開頭。

提示信息

示例 1

	輸入：l1 = [2,4,3], l2 = [5,6,4]
	輸出：[7,0,8]
	解釋：342 + 465 = 807

示例 2

	輸入：l1 = [0], l2 = [0]
	輸出：[0]

示例 3

	輸入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
	輸出：[8,9,9,9,0,0,0,1]

提示

• 每個鏈表中的節(jié)點數(shù)在范圍?[1, 100]?內(nèi)
• 0 <= Node.val <= 9
• 題目數(shù)據(jù)保證列表表示的數(shù)字不含前導(dǎo)零

實現(xiàn)邏輯

結(jié)點累加

這道題目將兩個鏈表結(jié)合成一個鏈表，比較清晰的思路就是，類似于四則運(yùn)算中的加法，從個位往高位進(jìn)行每一位相加，如果當(dāng)前位的結(jié)果大于等于 10 時則需要在高位加 1。

解析到程序當(dāng)中，既可以使用循環(huán)的方式，也可以使用遞歸的思維。循環(huán)的方式是將兩個鏈表同步遞增，而遞歸的方式是每次計算完一位時再對鏈表的下一個結(jié)點做遞歸處理。

通過循環(huán)的方式解決這個問題，時間復(fù)雜度是?O(n)，空間復(fù)雜度也是?O(n)，這里的 n 指的是最長的那個鏈表節(jié)點數(shù)。

	package cn.fatedeity.algorithm.leetcode;
	public class AddTwoNumbers {
	public ListNode answer(ListNode l1, ListNode l2) {
	ListNode result = new ListNode();
	ListNode listNode = result;
	boolean addOne = false;
	while (l1 != null || l2 != null || addOne) {
	int sum = 0;
	if (l1 != null) {
	sum += l1.val;
	l1 = l1.next;
	}
	if (l2 != null) {
	sum += l2.val;
	l2 = l2.next;
	}
	if (addOne) {
	sum += 1;
	}
	addOne = sum >= 10;
	listNode.next = new ListNode(sum % 10);
	listNode = listNode.next;
	}
	return result.next;
	}
	}
	class ListNode {
	int val;
	ListNode next;
	ListNode() {
	}
	ListNode(int val) {
	this.val = val;
	}
	ListNode(int val, ListNode next) {
	this.val = val;
	this.next = next;
	}
	}

?

?