【LeetCode】 445. 两数相加 II 链表头插法

谁践踏了优雅 2021-06-10 20:38 328阅读 0赞

## <table>   <tbody>    <tr>     <td><font>题目</font></td>    </tr>   </tbody>  </table> ##

题目传送门：[传送门（点击此处）][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]

## <table>   <tbody>    <tr>     <td><font>题解</font></td>    </tr>   </tbody>  </table> ##

### 思路 ###

思考好使用什么样的数据结构，这道题目不是很难  
![在这里插入图片描述][20200414202829769.png]

1.  由给出的demo可知，链表开始是高位，候面是低位，要考虑进位的问题
2.  直接向下进行相加是不合适的，我们做加法肯定不会从高位开始加，所以就要考虑变换顺序
3.  我们要从个位开始进行相加，遍历链表，放入栈中，再进行操作，我们就能从各位开始了
4.  这里还遇到一个问题，直接操作生成链表会变成相反的顺序，所以，在这里生成链表要使用头插法来进行

#### 将链表放入栈中 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70 1]

#### 头插法生成链表 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70 6]

### code ###

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
    class Solution { 
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) { 
    		Stack<Integer> stack1 = new Stack<>();
    		Stack<Integer> stack2 = new Stack<>();
    		while (l1 != null) { 
    			stack1.add(l1.val);
    			l1 = l1.next;
    		}
    		while (l2 != null) { 
    			stack2.add(l2.val);
    			l2 = l2.next;
    		}
    		ListNode head = null;
    		int flag = 0;
    		while (!stack1.isEmpty() || !stack2.isEmpty() || flag > 0) { 
    			int val1 = stack1.isEmpty() ? 0 : stack1.pop();
    			int val2 = stack2.isEmpty() ? 0 : stack2.pop();
    			int val = val1 + val2 + flag;
    			flag = val / 10;
    			val = val % 10;
    			ListNode temp = new ListNode(val);
    			temp.next = head;
    			head = temp;
    		}
    		return head;
        }
    }

[Link 1]: https://leetcode-cn.com/problems/add-two-numbers-ii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]: /images/20210529/a5b578d7bb904abd942d36006e2401a0.png
[20200414202829769.png]: /images/20210529/ece785e2b66a4ccaaaebe686a28d2a0e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70 1]: /images/20210529/ace1f16790b346d0a340788e72240b91.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70 2]: /images/20210529/c81913ef880d42cbb5eae53f802bd46e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70 3]: /images/20210529/6f6b77ba4b5c485dbcb7096d057e2839.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70 4]: /images/20210529/4cda8682969349efb1a449568bb00924.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70 5]: /images/20210529/42f8040376454255a16c8c9247824cd5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70 6]: /images/20210529/bbe38408ae7940d6a81fee5b99e65c72.png