專欄：50多種數(shù)據(jù)結(jié)構(gòu)徹底征服

專欄：50多種經(jīng)典圖論算法全部掌握

前幾天美攝科技在公眾號發(fā)文稱，字節(jié)跳動旗下抖音等8款產(chǎn)品代碼抄襲，判令抖音公司及其關(guān)聯(lián)公司立即停止侵害美攝SDK軟件著作權(quán)的行為，向美攝公司賠禮道歉，賠償經(jīng)濟(jì)損失及合理支出共計約8266.8萬元。

抄襲的原因據(jù)說是一位曾經(jīng)在美攝工作過的員工，離職兩年半后加入了字節(jié)，寫代碼時重復(fù)使用了一部分他在美攝工作時寫過的代碼。我之前一直以為代碼是開源的，自己寫的代碼可以隨便用，隨便ctrl+c，ctrl+v，現(xiàn)在看來也不行了。

我覺得這種事很多程序員都干過，在這家公司寫的代碼，到下家公司的時候，如果能用到會直接拿過來用，不可能自己在重寫一遍。原來這種行為是違法的，如果全部重寫一遍是不是就不涉嫌抄襲？如果這樣的話，法院又怎么確定代碼是上家拿過來的還是自己重寫的？

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第21題：合并兩個有序鏈表。

問題描述

來源：LeetCode第21題

難度：簡單

將兩個升序鏈表合并為一個新的升序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點(diǎn)組成的。

示例1：

輸入：l1 = [1,2,4], l2 = [1,3,4] 輸出：[1,1,2,3,4,4]

• 兩個鏈表的節(jié)點(diǎn)數(shù)目范圍是 [0, 50]

• -100 <= Node.val <= 100

• l1 和 l2 均按非遞減順序排列

問題分析

這題是讓合并兩個 有序 的鏈表，并且合并之后的鏈表也是有序的，很簡單的一道題，使用雙指針即可，兩個指針分別指向兩個鏈表的頭節(jié)點(diǎn)，哪個節(jié)點(diǎn)的值小就取哪個。

如果其中的一個鏈表已經(jīng)訪問完了，就不需要再比較了，把另一個鏈表剩下節(jié)點(diǎn)的連接到新的鏈表后面即可。

JAVA：

public ListNode mergeTwoLists(ListNode linked1, ListNode linked2) {     // 如果其中的一個鏈表為空，直接返回另一個鏈表     if (linked1 == null)         return linked2;     if (linked2 == null)         return linked1;     ListNode dummy = new ListNode();// 啞結(jié)點(diǎn)     ListNode tail = dummy; // 新鏈表的尾節(jié)點(diǎn)     // 如果這兩個鏈表都不為空，就一直遍歷     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; //更新尾節(jié)點(diǎn)     }     // 然后把那個不為空的鏈表掛到新的鏈表后面     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();// 啞結(jié)點(diǎn)         ListNode *tail = dummy; // 新鏈表的尾節(jié)點(diǎn)         // 如果這兩個鏈表都不為空，就一直遍歷         while (list1 && list2) {             // 比較一下，哪個小就把哪個連接到新的鏈表后面             if (list1->val <= list2->val) {                 tail->next = list1;// 連接到新的鏈表后面                 list1 = list1->next;// 在往后走一步             } else {// 同上                 tail->next = list2;                 list2 = list2->next;             }             tail = tail->next; //更新尾節(jié)點(diǎn)         }         // 然后把那個不為空的鏈表掛到新的鏈表后面         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()  # 啞結(jié)點(diǎn)     tail = dummy  # 新鏈表的尾節(jié)點(diǎn)     # 如果這兩個鏈表都不為空，就一直遍歷     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  # 更新尾節(jié)點(diǎn)     # 然后把那個不為空的鏈表掛到新的鏈表后面     tail.next = list1 if list1 else list2     return dummy.next  # 返回新的鏈表

筆者簡介

博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數(shù)據(jù)結(jié)構(gòu)和算法 的講解，在全球30多個算法網(wǎng)站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨(dú)特的解題思路和解題技巧，喜歡的可以給個關(guān)注，也可以 下載我整理的1000多頁的PDF算法文檔 。