题解 | #合并两个排序的链表#

import java.util.*;

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

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pHead1 ListNode类
     * @param pHead2 ListNode类
     * @return ListNode类
     */
    public ListNode Merge (ListNode pHead1, ListNode pHead2) {
        ListNode last = pHead1;
	  // 连接两个链表
        while (last != null) {
            ListNode next = last.next;
            if (next == null) {
                last.next = pHead2;
                break;
            }
            last = next;
        }
	  // 记录链表长度
        int size = 0;
        ListNode temp = pHead1;
        while (temp != null) {
            temp = temp.next;
            size++;
        }
	  // 冒泡排序法实现排序
        return sortMerge(pHead1, size);
    }

   public ListNode sortMerge(ListNode node, int size) {
        if (size == 0) {
		  // 递归结束条件
            return node;
        }
        ListNode temp = node;
        while (temp != null) {
		  // 这里循环可以优化，其实可以添加一个指针，记录循环次数，一旦大于size也就没有继续下去，减少不必要的循环次数
            ListNode next = temp.next;
            if (next != null) {
                int val = temp.val;
                int val1 = next.val;
			  // 每次比较相邻数据，前者大于后者，就交换值
                if (val > val1) {
                    next.val = val;
                    temp.val = val1;
                }
            }
            temp = temp.next;
        }
        return sortMerge(node, size - 1);
    }
}