剑指 Offer 25. 合并两个排序的链表

剑指offer最优解免费

本问题对应的 leetcode 原文链接：剑指 Offer 25. 合并两个排序的链表

问题描述

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

限制：

0 <= 链表长度 <= 1000

解题思路

视频讲解直达：本题视频讲解

代码实现

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode merge = new ListNode(0);
        ListNode temp = merge;

        while(l1 != null && l2 != null){
            if(l1.val < l2.val){

                temp.next = l1;
                l1 = l1.next;
            } else {
                temp.next = l2;
                l2 = l2.next;
            }

            temp = temp.next;
        }

        temp.next = l1 == null ? l2 : l1;

        return merge.next;
    }
}

时间复杂度：O(n+m)，n 和 m 表示两个链表长度
空间复杂度：O(1)

Python

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        merge = ListNode(0)
        temp = merge

        while l1 and l2:
            if l1.val < l2.val:
                temp.next = l1
                l1 = l1.next
            else:
                temp.next = l2
                l2 = l2.next

            temp = temp.next

        temp.next = l1 if l1 else l2

        return merge.next

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* merge = new ListNode(0);
        ListNode* temp = merge;

        while (l1 && l2) {
            if (l1->val < l2->val) {
                temp->next = l1;
                l1 = l1->next;
            } else {
                temp->next = l2;
                l2 = l2->next;
            }

            temp = temp->next;
        }

        temp->next = l1 ? l1 : l2;

        return merge->next;
    }
};

Go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    merge := &ListNode{}
    temp := merge

    for l1 != nil && l2 != nil {
        if l1.Val < l2.Val {
            temp.Next = l1
            l1 = l1.Next
        } else {
            temp.Next = l2
            l2 = l2.Next
        }

        temp = temp.Next
    }

    if l1 != nil {
        temp.Next = l1
    } else {
        temp.Next = l2
    }

    return merge.Next
}

JS

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    let merge = new ListNode(0);
    let temp = merge;

    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            temp.next = l1;
            l1 = l1.next;
        } else {
            temp.next = l2;
            l2 = l2.next;
        }

        temp = temp.next;
    }

    temp.next = l1 == null ? l2 : l1;

    return merge.next;
};

剑指offer题解

发表回复取消回复

后才能评论

control 普通 2024年12月6日下午10:01

    public ListNode trainningPlan(ListNode l1, ListNode l2) {

        ListNode newHead = new ListNode();
        ListNode tmpHead = newHead;
        while(l1 != null && l2 != null){
            if(l1.val > l2.val ){
                tmpHead.next = l2;
                l2 = l2.next;
                tmpHead = tmpHead.next;
            }else{
                tmpHead.next = l1;
                l1 = l1.next;
                tmpHead = tmpHead.next;
            }
        }
        tmpHead.next = l1 == null ? l2 : l1;
        return newHead.next;
    }

1: 常规的解题思路，重点是看清是升序还是降序
2: 对于合并链表，需要两个节点同时遍历，每次动小的那个
3:加油1206

HU 普通 2024年3月2日上午6:05

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var trainningPlan = function(l1, l2) {
    // 设置返回值的前一个节点和当前节点
    let res = new ListNode(-1);
    let cur = res;

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

    cur.next = l1 != null ? l1 : l2;

    return res.next;
};

杨帆普通 2022年10月31日下午5:44

class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode preNode = null;
ListNode headNode = null;
ListNode curNode = null;
while(l1 != null || l2 != null){
if(l1 null){
if(preNode null){
headNode = l2;
}else {
preNode.next = l2;
}
return headNode;
}
else if(l2 null){
if(preNode null){
headNode = l1;
}else {
preNode.next = l1;
}
return headNode;
}
else {
if (l1.val <= l2.val) {
curNode = l1;
l1 = l1.next;
} else {
curNode = l2;
l2 = l2.next;
}
if(preNode null){
headNode = curNode;
preNode = curNode;
}
preNode.next = curNode;
preNode = curNode;
}
}
return headNode;
}
}
时间复杂度o(1)，o(n)

登录以回复

Edison 普通 2022年10月23日下午8:34

定义一个虚拟头结点，也就是 dummy 节点，它相当于是个占位符，可以避免处理空指针的情况，降低代码的复杂性。

cpp代码

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(-1); //虚拟头节点
        ListNode* p = dummy;

        while (l1 != nullptr && l2 != nullptr) 
        {
            // 比较l1和l2两个指针
            // 将较小的节点放到p指针
            if (l1->val > l2->val) {
                p->next = l2;
                l2 = l2->next;
            }
            else {
                p->next = l1;
                l1 = l1->next;
            }
            // p指针不断向前进
            p = p->next;
        }
        // 如果l1还没有走完，直接把所有元素放到p后面
        if (l1 != nullptr) {
            p->next = l1;
        }

        // 如果l2还没有走完，直接把所有元素放到p后面
        if (l2 != nullptr) {
            p->next = l2;
        }

        // 返回头节点
        return dummy->next;
    }
};

Monster Dump 普通 2022年10月22日下午8:05

实现代码 (Java)

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }
        while (l1 != null) {
            curr.next = l1;
            l1 = l1.next;
            curr = curr.next;
        }
        while (l2 != null) {
            curr.next = l2;
            l2 = l2.next;
            curr = curr.next;
        }
        return dummy.next;
   }

时间复杂度: O(n+m)
空间复杂度: O(1)

勾陈一普通 2022年10月22日下午7:17

class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
// 参考归并排序，时间复杂度为O(m+n)
ListNode *p1 = l1, *p2 = l2;
ListNode *ans = new ListNode();

    ListNode *cur, *pre;
    pre = ans;
    while(p1 && p2)
    {
        cur = new ListNode();
        if(p1->val > p2->val)
        {
            cur->val = p2->val;
            p2 = p2->next;
        }
        else
        {
            cur->val = p1->val;
            p1 = p1->next;
        }
        pre->next = cur;
        pre = cur;
    }

    while(p1)
    {   
        cur = new ListNode();
        cur->val = p1->val;
        pre->next = cur;
        pre = cur;
        p1 = p1->next;
    }

    while(p2)
    {
        cur = new ListNode();
        cur->val = p2->val;
        pre->next = cur;
        pre = cur;
        p2 = p2->next;
    }
    return ans->next;
}

};

晨普通 2022年10月22日下午7:17

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        '''
        初始化
        创建伪节点dum
        创建节点cur指向dum
        '''
        dum = ListNode(0)
        cur = dum
        # 循环合并，当两个链表有一个为空是跳出循环
        while l1 and l2:
            if l1.val < l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next
            cur = cur.next
        #把链表剩余节点合并
        cur.next = l1 if l1 else l2
        return dum.next

时间复杂度O(n+m)
空间复杂度O(1)

波波_1936 普通 2022年10月22日下午5:25

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;

        ListNode preNode = new ListNode(-1);
        ListNode cu = preNode;

        while (l1 != null && l2 != null) {
            int val1 = l1.val;
            int val2 = l2.val;
            if (val1 < val2) {
                cu.next = l1;
                l1 = l1.next;
            } else {
                cu.next = l2;
                l2 = l2.next;
            }
            cu = cu.next;
        }
        if (l1 != null) {
            cu.next = l1;
        }
        if (l2 != null) {
            cu.next = l2;
        }
        return preNode.next;

    }

时间复杂度 O(n+m) 分别是两条链表的长度，也可以理解为O（n)
空间复杂度 O(1)

🚲南下普通 2022年10月22日下午3:14

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* pre = new ListNode(-1);
        ListNode* temp = pre; //移动temp指针
        while(l1!=nullptr && l2!=nullptr){
            if(l1->val < l2->val){
                temp->next = l1;
                l1 = l1->next;
            }else{
                temp->next = l2;
                l2 = l2->next;
            }
            temp = temp->next;
        }
        temp->next = l1nullptr?l2:l1;

    return pre->next;

}

};

Y7n05h 普通 2022年10月22日下午2:46

C++ 题解

class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode *head = nullptr;
        auto **cur = &head;
        if (!l1) return l2;
        if (!l2) return l1;
        while (true) {
            if (l1->val < l2->val) {
                *cur = l1;
                cur = &l1->next;
                l1 = l1->next;
                if (!l1) {
                    *cur = l2;
                    return head;
                }
            } else {
                *cur = l2;
                cur = &l2->next;
                l2 = l2->next;
                if (!l2) {
                    *cur = l1;
                    return head;
                }
            }
        }
    }
};

晨渊普通 2022年10月22日下午1:55

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
          //定义合并排序的链表节点
          ListNode *mergePtr = new ListNode();    //第一个vel=0
          ListNode *merge = mergePtr;
          while((l1!=NULL) && (l2!=NULL)){
          if(l1->val < l2->val){
              merge->next = l1;
              l1 = l1->next;
          }
          else{
              merge->next = l2;
              l2 = l2->next;
          }
          merge = merge->next; //下一个
          }
          merge->next = l1==NULL?l2:l1;    
          return mergePtr->next;      //下一个节点
    }
};

wxc 普通 2022年10月22日上午10:50

额

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if(l1 == None):
            return l2
        elif(l2 == None):
            return l1
        elif(l1.val <= l2.val):
            l1.next = self.mergeTwoLists(l1.next,l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1,l2.next)
            return l2