题解 | #牛群的能量值#

知识点：

1. 单链表的遍历与操作。
2. 逆序表示的链表相加。

题意分析：

题目描述了两群牛的能量值，能量值用链表表示，每个节点的值为能量值的一位数字。能量值按照逆序的方式存储在链表中，即链表的第一个节点表示个位，第二个节点表示十位，以此类推。现在需要将这两个逆序链表的能量值相加，然后以相同的逆序形式返回表示和的链表。

时间复杂度：

假设两个链表分别有M和N个节点。

1. 在代码中，我们需要遍历两个链表，进行逐位相加，并生成新的结果链表。在最坏情况下，需要遍历两个链表的所有节点，因此时间复杂度为O(max(M, N))。

代码分析：

代码中的解决思路是使用游标指针head1和head2同时遍历两个链表，然后逐位相加。通过维护一个进位值carry，来处理相加后的进位情况。同时，使用一个新的链表newHead来保存相加的结果。最后，检查是否有进位值为1，若有，需要添加一个新的节点作为最高位。

代码：

import java.util.*;

class ListNode {
    int val;
    ListNode next;

    public ListNode(int val) {
        this.val = val;
    }
}

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    public ListNode addEnergyValues(ListNode head1, ListNode head2) {
        // 创建一个新的头节点，并用 cur 指针指向头节点
        ListNode newHead = new ListNode(-1);
        ListNode cur = newHead;
        int carry = 0; // 进位值初始化为0

        // 循环遍历两个链表，直到两个链表都为空
        while (head1 != null || head2 != null) {
            // 获取当前节点的值，如果节点为空则用0代替
            int val1 = head1 != null ? head1.val : 0;
            int val2 = head2 != null ? head2.val : 0;

            // 计算当前位置的和以及进位值
            int sum = val1 + val2 + carry;
            int digit = sum % 10;
            carry = sum / 10;

            // 创建一个新的节点，并将其添加到结果链表中
            cur.next = new ListNode(digit);
            cur = cur.next;

            // 移动指针到下一个节点
            if (head1 != null) head1 = head1.next;
            if (head2 != null) head2 = head2.next;
        }

        // 最后检查进位值是否为1，若为1则需要添加一个新的节点作为最高位
        if (carry == 1) {
            cur.next = new ListNode(1);
        }

        // 返回结果链表的头节点的下一个节点，即去除头节点的结果链表
        return newHead.next;
    }
}