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

2023-12-13 05:11:29

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)。

文章来源:https://blog.csdn.net/Theolulu/article/details/134909941
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。