专栏：50多种数据结构彻底征服 专栏：50多种经典图论算法全部掌握 前几天美摄科技在公众号发文称，字节跳动旗下抖音等8款产品代码抄袭，判令抖音公司及其关联公司立即停止侵害美摄SDK软件著作权的行为，向美摄公司赔礼道歉，赔偿经济损失及合理支出共计约8266.8万元。 抄袭的原因据说是一位曾经在美摄工作过的员工，离职两年半后加入了字节，写代码时重复使用了一部分他在美摄工作时写过的代码。我之前一直以为代码是开源的，自己写的代码可以随便用，随便ctrl+c，ctrl+v，现在看来也不行了。 我觉得这种事很多程序员都干过，在这家公司写的代码，到下家公司的时候，如果能用到会直接拿过来用，不可能自己在重写一遍。原来这种行为是违法的，如果全部重写一遍是不是就不涉嫌抄袭？如果这样的话，法院又怎么确定代码是上家拿过来的还是自己重写的？ 
--------------下面是今天的算法题-------------- 来看下今天的算法题，这题是LeetCode的第21题：合并两个有序链表。 问题描述 来源：LeetCode第21题
难度：简单 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例1：
输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]
两个链表的节点数目范围是 [0, 50] -100 <= Node.val <= 100 l1 和 l2 均按非递减顺序排列
问题分析 这题是让合并两个 有序 的链表，并且合并之后的链表也是有序的，很简单的一道题，使用双指针即可，两个指针分别指向两个链表的头节点，哪个节点的值小就取哪个。 
如果其中的一个链表已经访问完了，就不需要再比较了，把另一个链表剩下节点的连接到新的链表后面即可。 JAVA： public ListNode mergeTwoLists(ListNode linked1, ListNode linked2) { // 如果其中的一个链表为空，直接返回另一个链表 if (linked1 == null) return linked2; if (linked2 == null) return linked1; ListNode dummy = new ListNode();// 哑结点 ListNode tail = dummy; // 新链表的尾节点 // 如果这两个链表都不为空，就一直遍历 while (linked1 != null && linked2 != null) { // 比较一下，哪个小就把哪个连接到新的链表后面 if (linked1.val <= linked2.val) { tail.next = linked1;// 连接到新的链表后面 linked1 = linked1.next;// 在往后走一步 } else {// 同上 tail.next = linked2; linked2 = linked2.next; } tail = tail.next; //更新尾节点 } // 然后把那个不为空的链表挂到新的链表后面 tail.next = linked1 == null ? linked2 : linked1; return dummy.next; // 返回新的链表 }
C++： public: ListNode *mergeTwoLists(ListNode *list1, ListNode *list2) { // 如果其中的一个链表为空，直接返回另一个链表 if (!list1) return list2; if (!list2) return list1; auto *dummy = new ListNode();// 哑结点 ListNode *tail = dummy; // 新链表的尾节点 // 如果这两个链表都不为空，就一直遍历 while (list1 && list2) { // 比较一下，哪个小就把哪个连接到新的链表后面 if (list1->val <= list2->val) { tail->next = list1;// 连接到新的链表后面 list1 = list1->next;// 在往后走一步 } else {// 同上 tail->next = list2; list2 = list2->next; } tail = tail->next; //更新尾节点 } // 然后把那个不为空的链表挂到新的链表后面 tail->next = list1 ? list1 : list2; return dummy->next; // 返回新的链表 }
Python： def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: # 如果其中的一个链表为空，直接返回另一个链表 if not list1: return list2 if not list2: return list1 dummy = ListNode() # 哑结点 tail = dummy # 新链表的尾节点 # 如果这两个链表都不为空，就一直遍历 while list1 and list2: # 比较一下，哪个小就把哪个连接到新的链表后面 if list1.val <= list2.val: tail.next = list1 # 连接到新的链表后面 list1 = list1.next # 在往后走一步 else: # 同上 tail.next = list2 list2 = list2.next tail = tail.next # 更新尾节点 # 然后把那个不为空的链表挂到新的链表后面 tail.next = list1 if list1 else list2 return dummy.next # 返回新的链表
笔者简介 博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。 | 
