LeetCode [简单]合并两个有序链表 （迭代

21. 合并两个有序链表 - 力扣（LeetCode）

思路：

使用迭代的方法合并链表。当两个链表都不为空时，比较两个链表的对应结点值，将值较小的结点合并到结果链表中，然后将对应链表的结点向后移动一步。如果一个链表为空，或者遍历完毕，则将另一个链表的剩下的部分合并到结果链表中。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode MergeTwoLists(ListNode list1, ListNode list2) {
        ListNode preHead = new ListNode(-1);
        ListNode pre = preHead;

        while(list1 != null && list2 != null)
        {
            if(list1.val < list2.val)
            {
                pre.next = list1;
                list1 = list1.next;
            }
            else
            {
                pre.next = list2;
                list2 = list2.next;
            }
            pre = pre.next;
        }
        pre.next = list1 == null ? list2 : list1;

        return preHead.next;
    }
}

• 时间复杂度：O(m+n)，其中 m 和 n 分别是两个链表的长度。合并过程中最多需要遍历两个链表中的每个结点一次。
• 空间复杂度：O(1)。