题解 | 链表相加(二)

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        Stack<ListNode> add1 = new Stack<>();
        Stack<ListNode> add2 = new Stack<>();
        while (head1 != null) {
            add1.push(head1);
            head1 = head1.next;
        }
        while (head2 != null) {
            add2.push(head2);
            head2 = head2.next;
        }
        int size = Math.max(add1.size(), add2.size());
        int prev = 0;
        Stack<ListNode> resultStack = new Stack<>();
        for (int i = 0; i < size; i++) {
            int a = add1.isEmpty() ? 0 : add1.pop().val;
            int b = add2.isEmpty() ? 0 : add2.pop().val;
            int sum = a + b + prev;
            int result = 0;
            if (sum >= 10) {
                result = sum - 10;
                prev = 1;
            } else  {
                result = sum;
                prev = 0;
            }
            resultStack.push(new ListNode(result));

        }
        if (prev == 1) {
            resultStack.push(new ListNode(1));
        }
        ListNode resultNode = null;
        ListNode current = null;
        while (!resultStack.isEmpty()) {
            if (resultNode == null) {
                resultNode = resultStack.pop();
                current = resultNode;
            } else {
                current.next = resultStack.pop();
                current = current.next;
            }
        }
        return resultNode;
    }

    public ListNode reverseListNode(ListNode node) {
        if (node == null) {
            return null;
        }
        ListNode current = node;
        ListNode prev = null;
        while(current!=null) {
            ListNode tmp = current.next;
            current.next = prev;
            prev = current;
            current = tmp;
        }
        return current;
    }
}

题目不复杂，但是要实现O（1）反转链表，本地反转，还是需要费一些功夫