84 双指针解两数相加

问题描述：给你两个非空链表，表示两个非负的整数，他们的每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字，请你将两个数相加，并以相同的形式返回一个表示和的链表。

双指针求解：定义两个指针分别指向两个非空链表，并在while循环中进行指针的更新，若存在一个指针为空，则跳出循环，并使得当前指针指向剩余的部分，剩余部分也需要进行进位操作。

public List<Integer> addTwoList(List<Integer>list1,List<Integer>list2)
{
int index1=0;
int index2=0;
int flagCarry=0;
List<Integer>list=new LinkedList<>();
while(index1<list1.size()&&index2<list2.size())
{
list.add((list1.get(index1)+list2.get(index2))%10+flagCarry);
if((list1.get(index1)+list2.get(index2))/10==1){flagCarry=1;}else{flagCarry=0;}
index1++;
index2++;
}


if(index1==list1.size()&&index2--list2.size())
{
if(flagCarry==1){list.add(1);}
}


if(index1<list1.size())
{
for(int i=index1;i<list1.size;i++)
{
list.add((list1.get(i)+flagCarry)%10);
flagCarry=(list1.get(i)+flagCarry)/10;
}
if(flagCarry==1){list.add(1);}
}

if(index2<list2.size())
{
for(int i=index2;i<list1.size;i++)
{
list.add((list2.get(i)+flagCarry)%10);
flagCarry=(list2.get(i)+flagCarry)/10;
}
???????if(flagCarry==1){list.add(1);}
}
???????return list;
}

递归求解：使用函数dfs进行递归求解，最后需要进行边界判断。

public List<Integer> dfs(List<Integr>list1,List<Integer>list2,int index1,int index2,int flagCarry,List<Integer>res)
{
if(index1==list1.size()&&index2==list2.size()){if(flagCarry==1){res.add(1);return res;}else{return res;}}



if(index1<list1.size()&&index2<list2.size())
{
res.add((list1.get(index1)+list2.get(index2))%10);
return dfs(list1,list2,index1+1,index2+1,(list1.get(index1)+list2.get(index2))/10,res);
}

if(index1<list1.size())
{
int flag=flagCarry;
for(int i=index1;i<list1.size();i++)
{
res.add((list1.get(index1)+flag)%10);
flag=(list1.get(index1)+flag)%10;
}
if(flag==1){res.add(1);return res;}
return res;
}
}

public List<Integer>Dfs(List<Integer>list1,List<integer>list2)
{
List<Integer>res=new LinkedList<Integer>();
return dfs(list1,list2,0,0,res);
}