每天一道leetcode21-合併兩個有序鏈表

• 2019 年 10 月 4 日
• 筆記

題目

leetcode21-合併兩個有序鏈表

中文鏈接：

https://leetcode-cn.com/problems/merge-two-sorted-lists/

英文鏈接：

https://leetcode.com/problems/merge-two-sorted-lists/

題目詳述

將兩個有序鏈表合併為一個新的有序鏈表並返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。

示例：

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

題目詳述

思路

1. 合併兩個有序鏈表，由於兩個鏈表是有序的，那麼就依次去比較兩個鏈表的當前節點的大小；首先新建一個頭結點temp，用來代表一個新的鏈表的頭結點。
2. 鏈表A和B，鏈表A的當前節點是節點A1，鏈表B的當前的節點是節點B1，然後去比較A1與B1的大小，如果A1比B1小，那麼temp的下一個節點就指向A1,同時鏈表A往下移動一個節點；
3. 如果比較A1與B1的大小，發現A1比B1大，那麼temp的下一個節點就指向B1，同時鏈表B往下移動一個節點；
4. 直到鏈表A或者鏈表B當中的一個鏈表為空了，那麼循環結束。
5. 最後比如說鏈表A為空了，那麼B可能不為空，所以temp的下一個節點指向B，這樣就把剩餘的B的節點接在了後面；
6. 最後如果鏈表B為空了，那麼A可能不為空，所以temp的下一個節點指向A，這樣就把剩餘的A鏈表的節點接在了temp的後面

程式碼

/**   * Definition for singly-linked list.   * public class ListNode {   *     int val;   *     ListNode next;   *     ListNode(int x) { val = x; }   * }   */  class Solution {      public ListNode mergeTwoLists(ListNode l1, ListNode l2) {          ListNode temp = new ListNode(-1);          ListNode result = temp;          while(l1 != null && l2 != null)          {              if(l1.val < l2.val)              {                  temp.next = l1;                  l1 = l1.next;                  temp = temp.next;              }else{                  temp.next = l2;                  l2 = l2.next;                  temp = temp.next;              }          }          if(l1 == null)              temp.next = l2;          if(l2 == null)              temp.next = l1;          return result.next;        }  }  

程式碼講解

1. 程式碼11-12行就是新建一個頭結點，result的作用就是用來返回頭結點，
2. 13-25行，就是思路中說的，依次比較鏈表A和B的當前節點大小，哪個小，那麼temp就指向哪個；
3. 26-29行就是，如果l1為空，那麼l2可能不為空，temp的next就指向l2;如果l2為空，那麼temp的next指向l1。
4. 最後由於最開始的時候新建了一個temp節點，所以要返回result的next就是合併後的開頭的節點。