每天一道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就是合并后的开头的节点。