合并两个有序链表
程序员文章站
2022-06-24 18:46:07
合并两个有序链表1、题目题目要求:将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例:输入:1->2->4, 1->3->4输出:1->1->2->3->4->42、代码2.1、代码思路preNode 为待排序节点的前驱结点, node1 和 node2 分别指向两个链表中待排序的节点,谁小谁就排在 preNode 后面进行比较:由于 node1 指向的节点的值较小,让...
合并两个有序链表
1、题目
-
题目要求:将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
-
示例:
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4
2、代码
2.1、代码思路
- preNode 为待排序节点的前驱结点, node1 和 node2 分别指向两个链表中待排序的节点,谁小谁就排在 preNode 后面
- 进行比较:由于 node1 指向的节点的值较小,让 preNode 指向 node1 指向的节点
- 然后 preNode 指针后移 ,node1 指针后移
- 再次进行比较:由于 node2 指向的节点的值较小,让 preNode 指向 node2 指向的节点
- 直至 node1 == null 或者 node2 == null
- 最后链表 2 还有剩余元素,将 preNode 指向 node2 指向的节点,将剩余元素接在新链表的最后
2.2、链表节点定义
//节点
class Node {
public Integer data;
public Node next;
public Node(Integer data) {
this.data = data;
}
public String toString() {
return data.toString();
}
}
2.3、链表的定义
//链表类
class SingleLinkedList {
public Node head = new Node(0);
public void add(Node node) {
// 首节点指针不能移动哦,需要定义辅助指针
Node preNode = head;
while (preNode.next != null) {
preNode = preNode.next;
}
preNode.next = node;
}
public void show() {
// 首节点指针不能移动哦,需要定义辅助指针
Node curNode = head.next;
while (curNode != null) {
System.out.print(curNode.data + "-->");
curNode = curNode.next;
}
System.out.println();
}
}
2.4、链表合并
public static SingleLinkedList merge(SingleLinkedList list1, SingleLinkedList list2) {
// 新链表的头结点
Node head = new Node(0);
// preNode 指向当前待排序节点的前一个节点
Node preNode = head;
// 设置新链表的头结点
SingleLinkedList mergeList = new SingleLinkedList();
mergeList.head = head;
// node1 初始值默认指向 list1 的首节点
Node node1 = list1.head.next;
// node2 初始值默认指向 list2 的首节点
Node node2 = list2.head.next;
// 当 node1 和 node2 其中一个为 null 时,就代表有一个链表已经到头啦
while (node1 != null && node2 != null) {
// 将值小的节点排在前面(升序排列),并且后移 node1 或 node2 指针
if (node1.data < node2.data) {
preNode.next = node1;
node1 = node1.next;
} else {
preNode.next = node2;
node2 = node2.next;
}
// preNode 后移,为下一次排序做准备
preNode = preNode.next;
}
// 最后链上还有剩余节点的链表
preNode.next = (node1 == null) ? node2 : node1;
// 返回合并后的链表
return mergeList;
}
2.5、测试代码
- 代码
public static void main(String[] args) {
SingleLinkedList list1 = new SingleLinkedList();
list1.add(new Node(1));
list1.add(new Node(3));
list1.add(new Node(5));
list1.add(new Node(7));
list1.add(new Node(9));
SingleLinkedList list2 = new SingleLinkedList();
list2.add(new Node(2));
list2.add(new Node(4));
list2.add(new Node(6));
list2.add(new Node(6));
list2.add(new Node(8));
list2.add(new Node(10));
list2.add(new Node(11));
list2.add(new Node(12));
// 合并链表
SingleLinkedList mergeList = merge(list1, list2);
System.out.println("合并后的链表如下~~~");
mergeList.show();
}
- 程序运行结果
合并后的链表如下~~~
1-->2-->3-->4-->5-->6-->6-->7-->8-->9-->10-->11-->12-->
2.6、全部代码
public class MergeList {
public static void main(String[] args) {
SingleLinkedList list1 = new SingleLinkedList();
list1.add(new Node(1));
list1.add(new Node(3));
list1.add(new Node(5));
list1.add(new Node(7));
list1.add(new Node(9));
SingleLinkedList list2 = new SingleLinkedList();
list2.add(new Node(2));
list2.add(new Node(4));
list2.add(new Node(6));
list2.add(new Node(6));
list2.add(new Node(8));
list2.add(new Node(10));
list2.add(new Node(11));
list2.add(new Node(12));
// 合并链表
SingleLinkedList mergeList = merge(list1, list2);
System.out.println("合并后的链表如下~~~");
mergeList.show();
}
public static SingleLinkedList merge(SingleLinkedList list1, SingleLinkedList list2) {
// 新链表的头结点
Node head = new Node(0);
// preNode 指向当前待排序节点的前一个节点
Node preNode = head;
// 设置新链表的头结点
SingleLinkedList mergeList = new SingleLinkedList();
mergeList.head = head;
// node1 初始值默认指向 list1 的首节点
Node node1 = list1.head.next;
// node2 初始值默认指向 list2 的首节点
Node node2 = list2.head.next;
// 当 node1 和 node2 其中一个为 null 时,就代表有一个链表已经到头啦
while (node1 != null && node2 != null) {
// 将值小的节点排在前面(升序排列),并且后移 node1 或 node2 指针
if (node1.data < node2.data) {
preNode.next = node1;
node1 = node1.next;
} else {
preNode.next = node2;
node2 = node2.next;
}
// preNode 后移,为下一次排序做准备
preNode = preNode.next;
}
// 最后链上还有剩余节点的链表
preNode.next = (node1 == null) ? node2 : node1;
// 返回合并后的链表
return mergeList;
}
}
//链表类
class SingleLinkedList {
public Node head = new Node(0);
public void add(Node node) {
// 首节点指针不能移动哦,需要定义辅助指针
Node preNode = head;
while (preNode.next != null) {
preNode = preNode.next;
}
preNode.next = node;
}
public void show() {
// 首节点指针不能移动哦,需要定义辅助指针
Node curNode = head.next;
while (curNode != null) {
System.out.print(curNode.data + "-->");
curNode = curNode.next;
}
System.out.println();
}
}
//节点
class Node {
public Integer data;
public Node next;
public Node(Integer data) {
this.data = data;
}
public String toString() {
return data.toString();
}
}
本文地址:https://blog.csdn.net/oneby1314/article/details/107590876
上一篇: 迅为4412——QT4开发手册
下一篇: DB2编程序技巧 (一)