讨论/《链表》 - 合并两个有序链表/
《链表》 - 合并两个有序链表
共 7 个回复
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}
5
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode node=new ListNode();
        ListNode result=node;
        while(l1!=null&&l2!=null){
            if(l1.val>l2.val){
                node.next=l2;
                l2=l2.next;
            }else{
                node.next=l1;
                l1=l1.next;
            }
            node=node.next;
        }
        if(l1!=null){
            node.next=l1;
        }else if(l2!=null){
             node.next=l2;
        }
        return result.next;
    }
}
2

Python3

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        """
        思路:通过一个哨兵节点,来依次连接连接两个有序链表小者
        方法: 双指针
        """
        prehead = ListNode(0)
        pred = prehead
        while l1 and l2:
            if l1.val <= l2.val:
                pred.next = l1
                l1 = l1.next
            else:
                pred.next = l2
                l2 = l2.next
            pred = pred.next
        # 直接指向剩下的不为空的节点
        pred.next = l1 if l1 is not None else l2
        return prehead.next

C语言的代码——暴力解法
执行结果:通过
执行用时:4 ms, 在所有 C 提交中击败了91.43%的用户
内存消耗:5.8 MB, 在所有 C 提交中击败了99.32%的用户

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    struct ListNode *pa = l1, *pb = l2, *prev;
    struct ListNode *New = malloc(sizeof(struct ListNode));
    if(l1 == NULL)  return l2;
    if(l2 == NULL)  return l1;
    prev = New;
    while(pa && pb){
        if(pa->val <= pb->val){
            prev->next = pa;
            pa = pa->next;
        }
        else{
            prev->next = pb;
            pb = pb->next;
        }
        prev = prev->next;
    }
    while(pa){
        prev->next = pa;
        pa = pa->next;
        prev = prev->next;
    }
    while(pb){
        prev->next = pb;
        pb = pb->next;
        prev = prev->next;
    }
    return New->next;
}

C语言的代码——递归算法
执行结果:通过
执行用时:4 ms, 在所有 C 提交中击败了91.43%的用户
内存消耗:5.9 MB, 在所有 C 提交中击败了76.67%的用户

//采用递归算法
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){ //目的:合并两个升序链表
    if(l1 == NULL){
        return l2;
    }
    if(l2 == NULL){
        return l1;
    }
    if(l1->val <= l2->val){ //比较两个升序链表表首结点元素的大小
        l1->next = mergeTwoLists(l1->next,l2);  //value小的结点的next指针域指向剩余链表部分最小的表头元素
        return l1;  //返回较小的结点
    }
    else{
        l2->next = mergeTwoLists(l1,l2->next);
        return l2;
    }
}
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1 == nil {
        return l2
    }
    if l2 == nil {
        return l1
    }
    if l1.Val < l2.Val {
        ret := mergeTwoLists(l1.Next,l2)
        l1.Next = ret
        return l1
    }else {
        ret := mergeTwoLists(l1,l2.Next)
        l2.Next = ret
        return l2
    }
}
1
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* head;
        ListNode* l1_curr;
        ListNode* l2_curr;
        ListNode* temp;
        if (l1 == nullptr)
            return l2;
        if (l2 == nullptr)
            return l1;
        if (l1->val <= l2->val) {
            head = l1;
            temp = head;
            l1_curr = l1->next;
            l2_curr = l2;
        }
        else {
            head = l2;
            temp = head;
            l1_curr = l1;
            l2_curr = l2->next;
        }
        while (l1_curr != nullptr && l2_curr != nullptr) {
            if (l2_curr == nullptr || l1_curr->val <= l2_curr->val) {
                temp->next = l1_curr;
                temp = l1_curr;
                l1_curr = l1_curr->next;
            }
            if (l1_curr == nullptr || l1_curr->val > l2_curr->val)
            {
                temp->next = l2_curr;
                temp = l2_curr;
                l2_curr = l2_curr->next;
            }
            
            }
        if (l1_curr != nullptr) {
            while (l1_curr != nullptr) {
                temp->next = l1_curr;
                temp = l1_curr;
                l1_curr = l1_curr->next;
            }
        }
        else {
            while (l2_curr != nullptr) {
                temp->next = l2_curr;
                temp = l2_curr;
                l2_curr = l2_curr->next;
            }
        }
        return head;
    }
};

归并思路,CPP实现:

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == nullptr) {
            return l2;
        }
        if (l2 == nullptr) {
            return l1;
        }
        auto point1 = l1;
        auto point2 = l2;
        ListNode *point = nullptr;
        ListNode *head = nullptr;
        while (point1 != nullptr && point2 != nullptr) {
            auto node = (point1->val < point2->val) ? point1 : point2;
            if (point == nullptr) {
                point = node;
                head = point;
            } else {
                point->next = node;
                if (point->next != nullptr) {
                    point = point->next;
                }
            }
            // 使用的链表切换到下一个节点
            if (point1->val < point2->val) {
                point1 = point1->next;
            } else {
                point2 = point2->next;
            }
        }
        if (point1 != nullptr) {
            while (point1 != nullptr) {
                point->next = point1;
                point = point->next;
                point1 = point1->next;
            }
        }
        if (point2 != nullptr) {
            while (point2 != nullptr) {
                point->next = point2;
                point = point->next;
                point2 = point2->next;
            }
        }
        return head;
    }
};