题解 | #链表相加(二)#
链表相加(二)
https://www.nowcoder.com/practice/c56f6c70fb3f4849bc56e33ff2a50b6b
利用Stack FILO的特性 先将 链表的每个值Push进Stack后 每次Pop出值; 时间空间复杂度都为O(n) using System; using System.Collections.Generic; /* public class ListNode { public int val; public ListNode next; public ListNode (int x) { val = x; } } */ class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head1 ListNode类 * @param head2 ListNode类 * @return ListNode类 */ public ListNode addInList (ListNode head1, ListNode head2) { // write code here Stack<int> st1 = new Stack<int>(); Stack<int> st2 = new Stack<int>(); ListNode result = null; int jingwei = 0; while(head1 != null){ st1.Push(head1.val); head1 = head1.next; } while(head2 != null){ st2.Push(head2.val); head2 = head2.next; } while(st1.Count != 0 || st2.Count != 0 || jingwei != 0 ){ int x = (st1.Count != 0) ? st1.Pop() : 0; int y = (st2.Count != 0) ? st2.Pop() : 0; int sum = x + y + jingwei; jingwei = sum/10; ListNode newNode = new ListNode(sum % 10); newNode.next = result; result = newNode; } return result; } }