两个有序链表合并成一个有序链表
算法:两个有序链表合并成一个有序链表(Java实现)
首先我们创建链表的结构类
@Getter
@Setter
class Node{
private Integer data; //存储数据
private Node next; //后继引用
public Node(Integer data) {
this.data = data;
}
}
准备数据:
//准备第一个有序链表
Node readyNode1(){
Node node = new Node(1);
Node node1 = new Node(6);
Node node2 = new Node(9);
Node node3 = new Node(10);
node.next = node1;
node1.next = node2;
node2.next = node3;
return node;
}
//准备第二个有序链表
Node readyNode2(){
Node node = new Node(2);
Node node1 = new Node(3);
Node node2 = new Node(8);
Node node3 = new Node(14);
Node node4 = new Node(22);
node.next = node1;
node1.next = node2;
node2.next = node3;
node3.next = node4;
return node;
}
我们想要实现链表的合并排列。
1.就要新建一个链表;
2.然后依次比较初始链表的大小;把数值小的放到新链表中,注意:只能放链表的值,不能放后继指针。
3.每次在新链表中插入数据的时候,都要保证插入的数据是在新链表的最后一个节点上。
代码如下:
//合并两个有序链表
public Node hebing(Node node1, Node node2){
if (node1 == null) return node2;
if (node2 == null) return node1;
Node node3 = null; //递归合并两个有序链表
while(node1 != null || node2 != null) {
Node n = new Node(); //每次循环使用一个Node去存储数据
if (node1 == null) {
getLastNode(node3).next = node2;
break;
} else if (node2 == null) {
getLastNode(node3).next = node1;
break;
} else if (node1.data > node2.data) {
n.data = node2.data;
node2 = node2.next;
} else if (node1.data <= node2.data) {
n.data = node1.data;
node1 = node1.next;
}
if (node3 == null) {
node3 = n;
} else {
getLastNode(node3).next = n;
}
}
return node3;
}
/**
* 获取链表的最后一级
*/
public Node getLastNode(Node node){
while (node != null){
if (node.next == null) {
return node;
} else {
node = node.next;
}
}
return null;
}
测试
@Test
public void run(){
Node node1 = readyNode1();
Node node2 = readyNode2();
Node hebing = hebing(node1, node2);
System.out.println(JSONObject.toJSONString(hebing));
}
输出结果:
{"data":1,"next":{"data":2,"next":{"data":3,"next":{"data":6,"next":{"data":8,"next":{"data":9,"next":{"data":10,"next":{"data":14,"next":{"data":22}}}}}}}}}
原文作者:&如歌的行板&
原文地址: https://blog.csdn.net/xupengbo527/article/details/89354832
本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
原文地址: https://blog.csdn.net/xupengbo527/article/details/89354832
本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
相关文章