一、题目内容

image.png

二、题解

解法1：

思路

双指针法

  • 生成一个临时节点，用作新链表的头
  • 比较两个链表的当前head，选取小的拼接在cur上
  • 当出现一个链表为空时，说明不为空的链表部分在整个链表里是直接有序的，拼接到cur上即可

  • 返回临时节点的next

    代码

    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.       ListNode dum = new ListNode(0), cur = dum;
    13.       while (l1 != null && l2 != null) {
    14.           if (l1.val < l2.val) {
    15.               cur.next = l1;
    16.               l1 = l1.next;
    17.           } else {
    18.               cur.next = l2;
    19.               l2 = l2.next;
    20.           }
    22.           cur = cur.next;
    23.       }
    25.       //不为空的直接拼接上去
    26.       cur.next = l1 != null ? l1 : l2;
    27.       return dum.next;
    28.   }
    29. }