您现在的位置是：首页 > 后台技术 > 数据结构与算法数据结构与算法

合并两个有序链表(图文)

第十三双眼睛2023-11-22【数据结构与算法】人已围观

简介合并两个有序链表
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

第一种方法是最简单，也最容易想到的，就是新建一个链表，然后按照顺序，把他们合成一个新的链表。代码如下：

public ListNode method1(ListNode list1, ListNode list2) {
   //定义一个新的链表,也存元素
   ListNode head = new ListNode();
   //定义两个指针，分别指向两个链表的头节点
   ListNode p1 = list1;
   ListNode p2 = list2;
   ListNode current = head;
   //先把头节点的值赋上去
   if (p1.val <= p2.val) {
       head.val = p1.val;
       p1 = p1.next;
   } else {
       head.val = p2.val;
       p2 = p2.next;
   }
   while (p1 != null && p2 != null) {
       if (p1.val <= p2.val) {
           current.next = new ListNode(p1.val);
           p1 = p1.next;
       } else {
           current.next = new ListNode(p2.val);
           p2 = p2.next;
       }
       current = current.next;
   }
   if (p1 != null) {
       current.next = p1;
   }
   if (p2 != null) {
       current.next = p2;
   }
   return head;
}

第二种方法：就是将两个链表根据元素大小重新连成一个新链表，主要思路也是比较，代码如下。

public ListNode method2(ListNode list1, ListNode list2) {
   if (list1 == null) {
       return list2;
   }
   if (list2 == null) {
       return list1;
   }
   ListNode p1 = list1;
   ListNode p2 = list2;
   ListNode head = null;
   ListNode current = null;
   if (p1.val <= p2.val) {
       head = p1;
       current = p1;
       p1 = p1.next;
   } else {
       head = p2;
       current = p2;
       p2 = p2.next;
   }
   while (p1 != null && p2 != null) {
       if (p1.val <= p2.val) {
           current.next = p1;
           p1 = p1.next;
           current = current.next;
       } else {
           current.next = p2;
           p2 = p2.next;
           current = current.next;
       }
   }
   if (p1 != null) {
       current.next = p1;
   }
   if (p2 != null) {
       current.next = p2;
   }
   return head;
}

Tags：

很赞哦！ ()

上一篇：有效的括号(图文)

下一篇：删除有序数组中的重复项(图文)