剑指offer——面试题17：合并两个排序的链表-CSDN博客

本文链接：https://blog.csdn.net/Allenlzcoder/article/details/79588018

本文提供了两种合并两个已排序链表的方法：一种是不使用额外的头节点直接合并，另一种则是利用辅助头节点进行合并。两种方法均通过比较当前节点值来决定合并顺序，并逐步推进直至所有元素被合并。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

增加复制头结点

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        if not l1 or not l2:
            return l1 if not l2 else l2
        dummy = ListNode(-1)
        cur = dummy
        cur1, cur2 = l1, l2
        while cur1 and cur2:
            if cur1.val <= cur2.val:
                cur.next = cur1
                cur1 = cur1.next
            else:
                cur.next = cur2
                cur2 = cur2.next
            cur = cur.next
        if cur1:
            cur.next = cur1
        if cur2:
            cur.next = cur2
        return dummy.next

Java

class Solution {
    public ListNode trainningPlan(ListNode l1, ListNode l2) {
        ListNode preHead = new ListNode(-1);
        ListNode cur = preHead;

        while (l1 != null || l2 != null) {
            if (l1 == null) {
                cur.next = l2;
                break;
            } else if (l2 == null) {
                cur.next = l1;
                break;
            } else if (l1.val <= l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else if (l1.val > l2.val) {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }

        return preHead.next;
    }
}

Solution1：
不要犯低级错误。。。

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2){
        if(pHead1 == NULL)
            return pHead2;
        else if(pHead2 == NULL)
            return pHead1;
        else{
            struct ListNode* ListMergeHead,*ListMergeTail,*temp1 = pHead1,*temp2 = pHead2;
            if(temp1->val <= temp2->val){ //找到头指针
                ListMergeHead = temp1;
                temp1 = temp1->next;
            }
            else {
                ListMergeHead = temp2;
                temp2 = temp2->next;
            }
            ListMergeTail=ListMergeHead;
            while(temp1 != NULL && temp2 != NULL){
                if(temp1->val <= temp2->val){
                    ListMergeTail->next = temp1;
                    ListMergeTail = ListMergeTail->next;
                    temp1 = temp1->next;
                }
                else{
                    ListMergeTail->next = temp2;
                    ListMergeTail = ListMergeTail->next;
                    temp2 = temp2->next;
                }
            }
            if(temp1 == NULL)
                ListMergeTail->next = temp2;
            else
                ListMergeTail->next = temp1;
            return ListMergeHead;
        }
    }
};