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

/**
 * @nc app=nowcoder id=d8b6b4358f774294a89de2a6ac4d9337 topic=295 question=23267 lang=Java
 * 2024-05-31 18:07:17
 * https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337?tpId=295&tqId=23267
 * [BM4] 合并两个排序的链表
 */

/** @nc code=start */

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) {
        // write code here
        
        if(pHead1 == null) {
            return pHead2;
        }        
        if(pHead2 == null) {
            return pHead1;
        }        

        int loop1HeadValue = pHead1.val;
        ListNode beforeLoop2 = pHead2;
        System.out.println("loop1HeadValue：" + loop1HeadValue);
        if(pHead2.val < pHead1.val) {
            while(beforeLoop2 != null) {            
                int loop2HeadValue = beforeLoop2.val;
                System.out.println("loop2HeadValue: " + loop2HeadValue);
                if(loop2HeadValue < loop1HeadValue &&  beforeLoop2.next != null && beforeLoop2.next.val < loop1HeadValue) {
                    beforeLoop2 = beforeLoop2.next;
                } else {
                    ListNode loop2Head = beforeLoop2;
                    beforeLoop2 = beforeLoop2.next;
                    loop2Head.next = pHead1;
                    pHead1 = pHead2;
                    pHead2 = beforeLoop2;
                    break;
                }
            }
        }
        

        
        if(pHead2 == null) {
            return pHead1;
        }

        ListNode loop1 = pHead1;
        ListNode loop2 = pHead2;

        while (true) {
            System.out.println("outside loop1:" + loop1.val);
            while (loop2 != null) {
                // System.out.println("loop2:" + loop2.val);
                // System.out.println("loop1:" + loop1.val);
                // System.out.println("loop1 next:" + loop1.next);
                if(loop2.val >= loop1.val && (loop1.next == null || loop2.val <= loop1.next.val)) {
                    ListNode swapTemp1 = loop1.next;                    
                    ListNode loop2Head = loop2;
                    // System.out.println("loop2Head:" + loop2Head.val);
                    loop2 = loop2.next;
                    loop1.next = loop2Head;
                    loop2Head.next = swapTemp1;
                    loop1 = loop1.next;
                } else {
                    break;
                }
            }
            loop1 = loop1.next;
            if(loop1 == null) {
                break;
            }
        }
        return pHead1;
    }
    
}

/** @nc code=end */