java编程题之合并两个排序的链表

本文实例为大家分享了java合并两个排序的链表，供大家参考，具体内容如下

/**
 *
 * 剑指offer编程题（JAVA实现)——第16题：合并两个排序的链表
 *
 * 输入两个单调递增的链表，输出两个链表合成后的链表， 当然我们需要合成后的链表满足单调不减规则。
 *
 */
public class Test16 {
 public static ListNode Merge(ListNode list1, ListNode list2) {
 if (list1 == null) { // 首先判断是否有链表为空
 return list2;
 } else if (list2 == null) {
 return list1;
 }
 ListNode end1 = list1;
 ListNode end2 = list2;
 ListNode tmp; //end1和end2分别代表两个链表，tmp用于中间合成链表

 if (end1.val > end2.val) {//把首节点小的链表看作end1
 tmp = end1;
 end1 = end2;
 end2 = tmp;
 } else {

 }
 ListNode newNode = end1;//用于最终返回的链表首节点

 while (end1.next != null && end2.next != null) { //将链表2中的元素插入链表1中合适的位置
 if (end1.val <= end2.val && end1.next.val >= end2.val) {
 tmp = end2.next;
 end2.next = end1.next;
 end1.next = end2;
 end1 = end2;
 end2 = tmp;
 } else {
 end1 = end1.next;
 }
 }

 if (end1.next == null) {//如果链表1到尾节点了则直接连接剩下的链表2中的首节点
 end1.next = end2;
 return newNode;
 } else {
 if (end1.next != null && end2.next == null) {//如果链表2到尾节点了则将链表2中所剩下的最后一个节点插入链表1
 while (end2 != null) {
  if (end1.val <= end2.val && end1.next.val >= end2.val) {
  end2.next = end1.next;
  end1.next = end2;
  break;
  } else {
  end1 = end1.next;
  if (end1.next == null) {//链表2最后的节点最大
  end1.next = end2;
  break;
  }
  }
 }
 }
 return newNode;
 }
 }

 public static void main(String[] args) {
 ListNode list1 = new ListNode(1);
 list1.next = new ListNode(3);
 list1.next.next = new ListNode(5);
 ListNode list2 = new ListNode(2);
 list2.next = new ListNode(4);
 list2.next.next = new ListNode(6);
 System.out.println(Merge(list2, list1));
 }

 // 链表
 public static class ListNode {
 int val;
 ListNode next = null;

 ListNode(int val) {
 this.val = val;
 }
 }
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • Java编程实现递增排序链表的合并

    题目描述 输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则. 解答: /* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { if(list1==null)

  • java编程题之合并两个排序的链表

    本文实例为大家分享了java合并两个排序的链表,供大家参考,具体内容如下 /** * * 剑指offer编程题(JAVA实现)--第16题:合并两个排序的链表 * * 输入两个单调递增的链表,输出两个链表合成后的链表, 当然我们需要合成后的链表满足单调不减规则. * */ public class Test16 { public static ListNode Merge(ListNode list1, ListNode list2) { if (list1 == null) { // 首先判断

  • python实现合并两个排序的链表

    剑指offer:合并两个排序的链表,Python实现 题目描述 输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则. 吐槽 本来想用递归实现,但是大脑卡壳,没有想到合适的递归策略,潜意识里还是把两个链表当成两个数组来看待,写出了非递归版本的代码.写完后回看自己写的代码,逻辑不够一目了然,中间变量过多,代码过长,一定不是好代码.上网查阅,发现一个如此美妙的递归版本,哇,写的好美啊!!!看来我对递归的了解和灵活应用还不够啊,至少在链表上还不够啊!!! 解题思路

  • C++实现合并两个排序的链表

    本文实例为大家分享了C++合并两个排序的链表,供大家参考,具体内容如下 问题描述 输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则. struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; 方法一 class Solution { public: ListNode* Merge(ListNode* pHead1, ListN

  • C++解决合并两个排序的链表问题

    C++解决合并两个排序的链表问题

    目录 题目描述: 示例: 解题思路: 测试代码: 题目描述: 输入两个递增的链表,单个链表的长度为n,合并这两个链表并使新链表中的节点仍然是递增排序的. 数据范围: n为0~1000,节点值为-1000~1000 要求:空间复杂度 O(1),时间复杂度 O(n) 如输入{1,3,5},{2,4,6}时,合并后的链表为{1,2,3,4,5,6},所以对应的输出为{1,2,3,4,5,6},转换过程如下图所示: 或输入{-1,2,4},{1,3,4}时,合并后的链表为{-1,1,2,3,4,4},所

  • TypeScript合并两个排序链表的方法详解

    TypeScript合并两个排序链表的方法详解

    目录 前言 思路分析 实现代码 测试用例 示例代码 前言 给定两个递增排序的链表,如何将这两个链表合并?合并后的链表依然按照递增排序.本文就跟大家分享一种解决方案,欢迎各位感兴趣的开发者阅读本文. 思路分析 经过前面的学习,我们知道了有关链表的操作可以用指针来完成.同样的,这个问题也可以用双指针的思路来实现: p1指针指向链表1的头节点 p2指针指向链表2的头节点 声明一个变量存储合并后的链表,比对两个指针指向的节点值大小: 如果p1指针指向的节点值比p2指向的值小,合并后的链表节点就取p1节点

  • Java编程通过匹配合并数据实例解析（数据预处理）

    Java编程通过匹配合并数据实例解析（数据预处理）

    本文研究的主要是Java编程通过匹配合并数据(数据预处理)的相关内容,具体如下. 数据描述 以下程序是对如下格式的数据进行合并处理. 这个表的每一行表示用户id及用户的特征.其中,一个用户只有一个特征向量,即第一列不会重复. 这张表的第一列,表示用户的id,第二列表示用户所看的电影,第三列表示用户对电影的打分(1-13分),第四列表示用户对电影的打分,但分值范围是1-5分. 问题描述 在做数据预处理时,如何将第二张表添加上用户特征呢?其实,方法很简单,将第二张表的用户id与第一张表的用户id进行

  • 对python实现合并两个排序链表的方法详解

    输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则. 1.迭代方法 def Merge(self, pHead1, pHead2): p1, p2 = pHead1, pHead2 if p1 and p2: if p1.val < p2.val: head = p1 p1 = p1.next else: head = p2 p2 = p2.next cur = head elif p1: return p1 else: return p2 while p

  • Java编程实现汉字按字母顺序排序的方法示例

    本文实例讲述了Java编程实现汉字按字母顺序排序的方法.分享给大家供大家参考,具体如下: String[] str0 = new String[]{"abd","ervcd","sdfc","abdc","sded","生活","文教","政治"}; String[] str1 = new String[]{"生活","

  • Java编程实现比对两个文本文件并标记相同与不同之处的方法

    本文实例讲述了Java编程实现比对两个文本文件并标记相同与不同之处的方法.分享给大家供大家参考,具体如下: 使用需求: 文件1里面是需要比较的内容,文件2是被比较的文本,现在需要找到在文件1中每一行的文本在文件2中是否存在并相等,如果相等,就在一份结果文件中输出,文件1的哪一行与文件2的哪一行相同,反之不相同就输出文件1的哪一行不相同货不存在. Java代码如下,输出的是result.txt文件,这个文件的行号和文件1保持一致,所以result中某一行的结果就是对应的文件1中这行数据在文件2中比

  • PHP实现合并两个排序链表的方法

    本文实例讲述了PHP实现合并两个排序链表的方法.分享给大家供大家参考,具体如下: 问题 输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则. 解决思路 简单的合并排序.由于两个数列本来就是递增的,所以每次将两个数列中较小的部分拿过来就可以了. 实现代码 <?php /*class ListNode{ var $val; var $next = NULL; function __construct($x){ $this->val = $x; } }*/ f

随机推荐