结果
image.png
思路
- 新建一个链表
- 然后建立两个结点，分别用于两个有序的单链表
- 然后比较大小，把数据填入新链表并有选择移动那两个结点
坑
SingleLinkedList类中的add（）方法原先是只考虑增加某单个结点heroNode，因此在增加节点的过程中直接改变了后继结点指向
heroNode.next=temp.next;
temp.next=heroNode
然而，当我们添加的结点heroNode不是单独的结点，而是属于其他链表时，这样的add（）方法就会使我们heroNode所在链表从heroNode这个位置截断，又后续结点断开连接，从而导致合并出错
解决办法：
新建一个结点newHeroNode=new HeroNode()，通过构造函数把传过来的heroNode的参数赋值给newHeroNode，然后我们改变newHeroNode即可，不会影响原链表。
在这里我们不必考虑内存影响。
加入我们要添加的使单独结点，创建newHeroNode后，heroNode无人可用，过一段时间，GC会自动回收heroNode的空间
如果传入的结点属于某个链表，更不用考虑内存了
核心代码
//合并两个有序的链表，合并后还是有序
public static HeroNode mergeTwoLinkedList(HeroNode head1, HeroNode head2) {
//如果其中一个为空，直接返回
if (head1.next == null) {
if (head2.next == null) {
System.out.println("两个链表均为空");
return null;
}
else {
return head2;
}
}
if (head2.next == null) {
return head1;
}
//新建一个链表
SingleLinkedList singleLinkedList = new SingleLinkedList();
//将两个结点，分别指向两个链表
HeroNode cur1 = head1.next;
HeroNode cur2 = head2.next;
while (cur1 != null || cur2 != null) {
if (cur1 == null) {
while (cur2 != null) {
singleLinkedList.add(cur2);
cur2=cur2.next;
}
break;
}
if (cur2 == null) {
while (cur1 != null) {
singleLinkedList.add(cur1);
cur1=cur1.next;
}
break;
}
if (cur1.number < cur2.number) {
singleLinkedList.add(cur1);
cur1 = cur1.next;
}
else if(cur1.number==cur2.number){
singleLinkedList.add(cur1);
cur1=cur1.next;
//由于该程序无法添加相同序号的元素，因此抛弃cur2
cur2=cur2.next;
}
else {
singleLinkedList.add(cur2);
cur2=cur2.next;
}
}
return singleLinkedList.getHead();
}
测试代码
package com.nan;
import java.util.Stack;
/**
* @author klr
* @create 2020-07-01-23:07
*/
public class SingleLinkedListDemo {
public static void main(String[] args) {
HeroNode hero4 = new HeroNode(4, "林冲4", "豹子头");
HeroNode hero10 = new HeroNode(8, "林冲8", "豹子头");
HeroNode hero1 = new HeroNode(1, "宋江1", "及时雨");
HeroNode hero2 = new HeroNode(2, "卢俊义2", "玉麒麟");
HeroNode hero3 = new HeroNode(3, "吴用3", "智多星");
SingleLinkedList singleLinkedList = new SingleLinkedList();
singleLinkedList.add(hero1);
singleLinkedList.add(hero2);
singleLinkedList.add(hero3);
singleLinkedList.add(hero4);
singleLinkedList.add(hero10);
System.out.println("修改前");
singleLinkedList.list();
singleLinkedList.update(new HeroNode(1,"小宋","及时雨"));
System.out.println("修改后");
singleLinkedList.list();
System.out.println("删除结点2");
singleLinkedList.delete(2);
singleLinkedList.list();
System.out.println("查找链表的第K个结点,从1开始");
System.out.println(singleLinkedList.getKNode(singleLinkedList.getHead(), 3));
System.out.println("翻转链表");
SingleLinkedList.reverseLinkedList(singleLinkedList.getHead());
singleLinkedList.list();
System.out.println("翻转链表后会改变原来结构，让我们看下逆序打印是否跟原链表打印一样");
SingleLinkedList.reversePrint(singleLinkedList.getHead());
System.out.println("测试合并不同链表");
HeroNode hero5 = new HeroNode(5, "林冲5", "豹子头");
HeroNode hero7 = new HeroNode(7, "宋江7", "及时雨");
HeroNode hero6 = new HeroNode(6, "卢俊义6", "玉麒麟");
HeroNode hero8 = new HeroNode(8, "吴用8", "智多星");
HeroNode hero9 = new HeroNode(4, "林冲9", "智多星");
SingleLinkedList singleLinkedList1 = new SingleLinkedList();
singleLinkedList1.add(hero5);
singleLinkedList1.add(hero6);
singleLinkedList1.add(hero7);
singleLinkedList1.add(hero8);
singleLinkedList1.add(hero9);
System.out.println("链表一：");
//因为要求链表有序，所以翻转回原来链表
SingleLinkedList.reverseLinkedList(singleLinkedList.getHead());
singleLinkedList.list();
System.out.println("链表二");
singleLinkedList1.list();
System.out.println("合并后链表");
// SingleLinkedList.mergeTwoLinkedList(singleLinkedList.getHead(), singleLinkedList1.getHead());
SingleLinkedList.printListByHead(SingleLinkedList.mergeTwoLinkedList(singleLinkedList.getHead(), singleLinkedList1.getHead()));
}
}
class SingleLinkedList{
//头结点，不能动，不存放具体的数据
private HeroNode head = new HeroNode(0,"","");
//合并两个有序的链表，合并后还是有序
public static HeroNode mergeTwoLinkedList(HeroNode head1, HeroNode head2) {
//如果其中一个为空，直接返回
if (head1.next == null) {
if (head2.next == null) {
System.out.println("两个链表均为空");
return null;
}
else {
return head2;
}
}
if (head2.next == null) {
return head1;
}
//新建一个链表
SingleLinkedList singleLinkedList = new SingleLinkedList();
//将两个结点，分别指向两个链表
HeroNode cur1 = head1.next;
HeroNode cur2 = head2.next;
while (cur1 != null || cur2 != null) {
if (cur1 == null) {
while (cur2 != null) {
singleLinkedList.add(cur2);
cur2=cur2.next;
}
break;
}
if (cur2 == null) {
while (cur1 != null) {
singleLinkedList.add(cur1);
cur1=cur1.next;
}
break;
}
if (cur1.number < cur2.number) {
singleLinkedList.add(cur1);
cur1 = cur1.next;
}
else if(cur1.number==cur2.number){
singleLinkedList.add(cur1);
cur1=cur1.next;
//由于该程序无法添加相同序号的元素，因此抛弃cur2
cur2=cur2.next;
}
else {
singleLinkedList.add(cur2);
cur2=cur2.next;
}
}
return singleLinkedList.getHead();
}
//逆序打印
//使用栈就可以实现
public static void reversePrint(HeroNode head) {
if (head.next == null) {
return;
}
Stack<HeroNode> heroNodes = new Stack<>();
HeroNode cur = head.next;
while (cur!=null) {
heroNodes.push(cur);
cur = cur.next;
}
while (!heroNodes.empty()) {
System.out.println(heroNodes.pop());
}
}
//翻转链表
public static HeroNode reverseLinkedList(HeroNode head){
if (head.next == null||head.next.next==null) {
return head;
}
//prev
HeroNode prev = null;
//cur
HeroNode cur = head.next;
//next
HeroNode next = null;
while (cur != null) {
next = cur.next;
cur.next = prev;
prev=cur;//当cur为空时，prev就为最后一个结点
cur=next;
}
head.next=prev;
return head;
}
public HeroNode getHead() {
return head;
}
//求链表的长度
public static int getLength(HeroNode head){
if (head.next == null) {
return 0;
}
HeroNode cur = head.next;
int count=0;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
//查找单链表的倒数第K个结点
//参数：head和k
public HeroNode getKNode(HeroNode head, int k) {
if (head.next == null) {
return null;
}
if (getLength(head) < k||k<=0) {
System.out.println(("参数小于1或者大于链表长度，无法查找"));
return null;
}
int position = getLength(head) - k + 1;//也可以去掉+1，后面的position>=0
HeroNode temp = head;
while (position >= 1) {
position--;
temp = temp.next;
}
return temp;
}
//找到当前链表的最后结点
//将最后这个结点的next指向新的结点
public void add(HeroNode heroNode){
//有可能传进来的是某个链表的其中一个结点，为了防止改变原关系，我们新建一个结点
HeroNode newHeroNode=new HeroNode(heroNode);
//因为head结点不动，我们需要定义一个零时结点
HeroNode temp = head;
//判断英雄是否重复
boolean flag = false;
while (true) {
if (temp.next == null) {
break;
}
if (temp.next.number > heroNode.number) {
break;
} else if (temp.next.number == heroNode.number) {
flag = true;//说明该英雄存在，无法添加
break;
}
temp = temp.next;
}
if (flag) {
System.out.printf("英雄%d存在，无法添加\n",heroNode.number);
return;
}
newHeroNode.next=temp.next;
temp.next=newHeroNode;
// //遍历这个链表，找到最后
// while (true) {
// //列表为空，直接添加
// if (temp.next == null) {
// temp.next = heroNode;
// break;
// }
// //比较大小，直接插入
// if (temp.number <= heroNode.number && heroNode.number <= temp.next.number) {
// heroNode.next = temp.next;
// temp.next = heroNode;
// break;
// }
// //如果没有找到，就继续找
// temp = temp.next;
// }
}
//根据id修改结点
public void update(HeroNode newHeroNode) {
if (head.next == null) {
System.out.println("链表为空，无法修改");
return;
}
HeroNode temp = head.next;
boolean flag = false;
while (true) {
if (temp == null) {
break;//已经遍历完链表
}
if (temp.number == newHeroNode.number) {
flag=true;
break;
}
temp=temp.next;
}
if (flag) {
temp.name = newHeroNode.name;
temp.nickName = newHeroNode.nickName;
}
else {
System.out.printf("未找到编号为%d的英雄\n",newHeroNode.number);
}
}
//删除结点
public void delete(int number) {
HeroNode temp = head;
if (temp.next == null) {
System.out.println("该链表为空");
return;
}
boolean flag = false;
while (true) {
if (temp.next == null) {
break;//遍历完链表
}
if (temp.next.number == number) {
flag = true;//找到结点
break;
}
temp=temp.next;
}
if (flag) {
temp.next=temp.next.next;
}
else {
System.out.printf("编号%d的英雄不存在",number);
}
}
//遍历
public void list(){
//判断链表是否为空
if (head.next == null) {
System.out.println("链表为空");
return;
}
//因为head不能动
HeroNode temp = head.next;
while (true) {
//判断是否到链表最后
if (temp == null) {
break;
}
//输出结点信息
System.out.println(temp);
//将temp后移
temp = temp.next;
}
}
//静态遍历
public static void printListByHead(HeroNode head){
//判断链表是否为空
if (head.next == null) {
System.out.println("链表为空");
return;
}
//因为head不能动
HeroNode temp = head.next;
while (true) {
//判断是否到链表最后
if (temp == null) {
break;
}
//输出结点信息
System.out.println(temp);
//将temp后移
temp = temp.next;
}
}
}
class HeroNode {
public int number;//排名
public String name;//姓名
public String nickName;//绰号
public HeroNode next;//指针
public HeroNode(int number, String name, String nickName) {
this.number = number;
this.name = name;
this.nickName = nickName;
}
public HeroNode(HeroNode heroNode) {
this.number=heroNode.number;
this.name=heroNode.name;
this.nickName=heroNode.nickName;
this.next=null;
}
@Override
public String toString() {
return "HeroNode{" +
"number=" + number +
", name='" + name + '\'' +
", nickName='" + nickName +
'}';
}
}
网友评论