题解 | #合并两群能量值#

知识点：

1. 单链表的遍历与操作。
2. 合并两个有序链表。

题意分析：

题目描述了两群牛的能量值，能量值用链表表示，每个节点的值为能量值。每群牛的能量值已经按照非递增顺序排列。现在需要将这两个链表的能量值合并为一个新的非递增链表，并返回这个新链表的头节点。

时间复杂度：

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

1. 在代码中，我们需要遍历两个链表，将能量值按非递增顺序合并为一个新的链表。在最坏情况下，需要遍历两个链表的所有节点，因此时间复杂度为O(M + N)。

代码分析：

代码中的解决思路是使用两个游标指针l1和l2同时遍历两个链表。比较当前节点的值，选择较大的值连接到新链表中，同时将游标指向下一个节点。直到有一个链表走完，就将剩下的链表连接到新链表的尾部。

代码：

import java.util.*;

class ListNode {
    int val;
    ListNode next;

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

public class Solution {
    /**
     * 合并两个链表的能量值，返回合并后的链表头节点
     *
     * @param l1 ListNode类 第一个链表的头节点
     * @param l2 ListNode类 第二个链表的头节点
     * @return ListNode类 合并后的链表头节点
     */
    public ListNode mergeEnergyValues(ListNode l1, ListNode l2) {
        // 创建一个临时头结点temp，并初始化一个游标cur指向temp
        ListNode temp = new ListNode(-1);
        ListNode cur = temp;

        // 循环条件：只有当两个链表都不为null才进入循环，只要有一个链表走完了，就跳出循环
        while (l1 != null && l2 != null) {
            int val;
            // 选择值大的那个链表，并将游标指向下一个节点，以便继续比较
            if (l1.val > l2.val) {
                val = l1.val;
                l1 = l1.next;
            } else {
                val = l2.val;
                l2 = l2.next;
            }

            // 利用游标cur连接当前节点，并将游标后移，以便下一次连接
            cur.next = new ListNode(val);
            cur = cur.next;
        }

        // 根据null判断哪个链表已经走到了尾部，选择另外一个没有走完的链表即可
        cur.next = l1 == null ? l2 : l1;

        // 返回合并后的链表头节点（跳过临时头结点temp）
        return temp.next;
    }
}