前言

不同长度的链表进行加法运算，需要先翻转链表，再进行对应相加以及进位操作。如果不允许翻转，可以采用数据结构栈来完成类似于回溯操作（先到底，再出来。）。但是栈有更好的灵活性。

一、案例

二、题解

1、翻转链表

package com.xhu.offer.offerII;import java.util.List;//反转链表
public class ReverseList {//迭代版public ListNode reverseList(ListNode head) {if (head == null) return null;ListNode pre = null, cur = head;while (cur.next != null) {ListNode newCur = cur.next;cur.next = pre;pre = cur;cur = newCur;}cur.next = pre;return cur;}//递归版public ListNode reverseList2(ListNode head) {//利用回溯解题if (head == null || head.next == null) return head;ListNode root = reverseList2(head.next);head.next.next = head;head.next = null;return root;}// Definition for singly-linked list.public class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) {this.val = val;}ListNode(int val, ListNode next) {this.val = val;this.next = next;}}}

2、翻转链表+链表相加

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {//先反转链表，再进行逐一加和进位。l1 = reverseList(l1);l2 = reverseList(l2);ListNode p1 = l1, p2 = l2, dummyHead = new ListNode(0), pre = dummyHead;int n = 0;while (p1 != null && p2 != null) {int num = p1.val + p2.val + n;n = num / 10;ListNode p = new ListNode(num - n * 10);pre.next = p;pre = p;p1 = p1.next;p2 = p2.next;}ListNode p = p1 == null ? p2 : p1;while (p != null) {int num = p.val + n;n = num / 10;ListNode node = new ListNode(num - n * 10);pre.next = node;pre = node;p = p.next;}if (n != 0) {ListNode node = new ListNode(n, null);pre.next = node;}return reverseList(dummyHead.next);}//递归版public ListNode reverseList(ListNode head) {//利用回溯解题if (head == null || head.next == null) return head;ListNode root = reverseList(head.next);head.next.next = head;head.next = null;return root;}

3、栈模拟回溯

public ListNode addTwoNumbers2(ListNode l1, ListNode l2) {//不能修改链表，即反转链表.//用栈存入Stack<Integer> s1 = new Stack<>(), s2 = new Stack<>();while (l1 != null || l2 != null) {if (l1 != null) {s1.add(l1.val);l1 = l1.next;}if (l2 != null) {s2.add(l2.val);l2 = l2.next;}}int n = 0;ListNode behind = null;while (!(s1.isEmpty() && s2.isEmpty())) {int num = n;num += s1.isEmpty() ? 0 : s1.pop();num += s2.isEmpty() ? 0 : s2.pop();n = num / 10;ListNode node = new ListNode(num - n * 10, behind);behind = node;}if (n == 0) return behind;return new ListNode(n, behind);}// Definition for singly-linked list.public class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) {this.val = val;}ListNode(int val, ListNode next) {this.val = val;this.next = next;}}

总结

1）链表反转可以采用迭代方式或者递归方式。
2）采用栈方式可以模拟回溯操作，多栈比起多递归还具有灵活性，即限制范围没多递归那么小。多递归必须要求问题能拆解成多个一样的小问题。

参考文献

[1] LeetCode 原题