题目链接

示例

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

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

解题思路

两个递增的链表
合并
新链表中的节点仍然是递增排序

解题思路：

  1. 定义伪头结点，当前位置指向伪头结点
  2. 开始循环 l1!=null && l2 !=null
  3. 判断，如果当前节点处，l1.val < l2.val 那么cur.next = l1 , l1 = l1.next , cur = cur.next
  4. 如果l1.val > l2.val 。 则相反
  5. 循环退出的边界条件，有两种，
    1. 长度一样，且循环到头了,
    2. 长度不一样，某一个没有循环到头
  6. 三元表达式，cur.next指向长链表的剩余节点处

  7. 返回链表的头结点，应该是伪节点的下一个节点


    注意：
    需要对原始链表进行操作，不能将原始链表赋值给临时变量操作

    代码

  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode(int x) { val = x; }
  7.  * }
  8.  */
  9. class Solution {
  10.     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
  11.         /*
  12.             两个递增的链表
  13.             合并
  14.             新链表中的节点仍然是递增排序
  16.             解题思路：
  17.             1. 定义伪头结点，当前位置指向伪头结点
  18.             2. 开始循环 l1!=null && l2 !=null
  19.             3. 判断，如果当前节点处，l1.val < l2.val 那么cur.next = l1 , l1 = l1.next , cur = cur.next
  20.             4. 如果l1.val > l2.val 。 则相反
  21.             5. 循环退出的边界条件，有两种，
  22.                 1.长度一样，且循环到头了，
  23.                 2.长度不一样，某一个没有循环到头
  24.             6. 三元表达式，cur.next指向长链表的剩余节点处
  25.             7. 返回链表的头结点，应该是伪节点的下一个节点
  27.             注意：
  28.             需要对原始链表进行操作，不能将原始链表赋值给临时变量操作
  30.         */
  32.         ListNode dum = new ListNode(0);
  33.         ListNode cur = dum;
  34.         while(l1!=null && l2!=null){
  35.             if(l1.val < l2.val){
  36.                 cur.next = l1;
  37.                 l1 = l1.next;
  38.             }else{
  39.                 cur.next = l2;
  40.                 l2 = l2.next;
  41.             }
  42.             cur = cur.next;    
  43.         }
  45.         cur.next = l1 != null ? l1 : l2;
  46.         return dum.next;
  48.     }
  49. }