BM4 合并两个排序的链表

描述

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
数据范围： 0≤n≤1000，−1000≤节点值≤1000
要求：空间复杂度 O(1)，时间复杂度 O(n)

如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}，转换过程如下图所示：

输入：
{1,3,5},{2,4,6}

返回值：
{1,2,3,4,5,6}

递归

解题思路：
特殊情况：如果有一个链表为空，返回另一个链表
如果pHead1 节点值比小pHead2，下一个节点应该是 pHead1，应该return pHead1，在return之前，指定pHead1的下一个节点应该是pHead1.next和pHead2俩链表的合并后的头结点
如果pHead1 节点值比pHead2大，下一个节点应该是pHead2，应该return pHead2，在return之前，指定pHead2的下一个节点应该是pHead1和pHead2.next俩链表的合并后的头结点

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        // list1 list2为空的情况
        if(list1 == null || list2 == null){
            return list1 != null ? list1 : list2;
        }
        // 两个链表元素依次对比
        if(list1.val <= list2.val){
            // 递归计算 list1.next, list2
            list1.next = Merge(list1.next, list2);
            return list1;
        }else{
            // 递归计算 list1, list2.next
            list2.next = Merge(list1, list2.next);
            return list2;
        } 
    }
}

借助额外数组

解题思路：
(1) 创建额外存储数组 nums
(2) 依次循环遍历 pHead1, pHead2，将链表中的元素存储到 nums中，再对nums进行排序
(3) 依次对排序后的数组 nums取数并构建合并后的链表

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        // list1 list2为空的情况
        if(list1==null) return list2;
        if(list2==null) return list1;
        if(list1 == null && list2 == null){
            return null;
        }
        //将两个两个链表存放在list中
        ArrayList<Integer> list = new ArrayList<>();
        // 遍历存储list1
        while(list1!=null){
            list.add(list1.val);
            list1 = list1.next;
        }
        // 遍历存储list2
        while(list2!=null){
            list.add(list2.val);
            list2 = list2.next;
        }
        // 对 list 排序
        Collections.sort(list);
        // 将list转换为 链表
        ListNode newHead = new ListNode(list.get(0));
        ListNode cur = newHead;
        for(int i=1;i<list.size();i++){
            cur.next = new ListNode(list.get(i));
            cur = cur.next;
        }
        // 输出合并链表
        return newHead;
    }
}

迭代

设置result为哑结点，放置于新链表之前，最后返回的就是result.next；设置cur为当前节点，从result开始
当两个链表都非空时进入循环，令新链表的下一个节点cur.next为val更小的节点，相应的链表节点后移一位，每次循环记得cur也要后移一位
如果循环结束后还有链表非空，cur指向非空链表，返回result.next

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
        
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        if not pHead1:
            return pHead2
        if not pHead2:
            return pHead1
        
        result = ListNode(-1)
        cur = result
        while pHead1 and pHead2:
            # 元素对比
            if pHead1.val <= pHead2.val:
                cur.next = pHead1
                pHead1 = pHead1.next
            else:
                cur.next = pHead2
                pHead2 = pHead2.next
            # 指针右移动一位
            cur = cur.next
        # 拼接未对比的链表
        cur.next = pHead1 if pHead1 else pHead2
        return result.next

self

package com.company;

public class Merge {

	public static void main(String[] args) {
		ListNode listNode1 = new ListNode(1);
		ListNode listNode2 = new ListNode(2);
		ListNode listNode3 = new ListNode(3);
		ListNode listNode4 = new ListNode(4);
		ListNode listNode5 = new ListNode(5);
		ListNode listNode6 = new ListNode(6);

		listNode1.next = listNode3;
		listNode3.next = listNode5;
		listNode2.next = listNode4;
		listNode4.next = listNode6;

		ListNode result = Merge(listNode1, listNode2);
		System.out.println("111");
	}

	public static ListNode Merge(ListNode list1, ListNode list2) {
		ListNode result = new ListNode(-1);
		ListNode p = result;
		ListNode p1 = list1;
		ListNode p2 = list2;
		while (true) {
			if (p1 == null) {
				p.next = p2;
				break;
			}
			if (p2 == null) {
				p.next = p1;
				break;
			}

			if (p1.val <= p2.val) {
				p.next = p1;
				p = p.next;
				p1 = p1.next;
			} else {
				p.next = p2;
				p = p.next;
				p2 = p2.next;
			}
		}
		return result.next;
	}
}