合并有序两个单链表,合并后链表依然有序
2020-06-02 16:09:09来源:博客园 阅读 ()
合并有序两个单链表,合并后链表依然有序
最近在学习数据结构,特此记录一下,方便以后查阅.
1 //定义一个类来管理我们的英雄 也就是链表 2 class SingleLinkedList{ 3 //先初始化一个头节点,头节点不能动,用于寻找链表的头 4 private HeroNode head = new HeroNode(0,"",""); 5 6 public HeroNode getHead() { 7 return head; 8 } 9 10 11 public void addOrderByNo(HeroNode heroNode){ 12 //定义一个变量来辅助遍历 13 HeroNode temp = head; 14 boolean flag = false;//用来判断数据书否存在的 15 16 while (true){ 17 //为链表的最后 18 if(temp.next==null){ 19 break; 20 } 21 //如果下一个节点的数字已经大于现在要添加的数了 证明已经找到了 当前要添加的位置 22 if(temp.next.no>heroNode.no){ 23 break; 24 } 25 //如果等于要添加的数 证明这个数据已经添加过了 不能在添加 26 if(temp.next.no==heroNode.no){ 27 flag = true;//证明存在 28 break; 29 } 30 //没找到后移temp 31 temp = temp.next; 32 } 33 34 //判断flag的值 35 if(!flag){ 36 //插入数据到链表中 37 //1.先将添加的数据的next指向下一个数据 38 heroNode.next = temp.next; 39 //2.再将temp的next指向添加的数据 40 temp.next = heroNode; 41 }else{ 42 System.out.printf("准备插入的英雄的编号 %d 已经存在了, 不能加入\n", heroNode.no); 43 } 44 } 45 } 46 47 class HeroNode{ 48 public int no; 49 public String name; 50 public String nickname; 51 public HeroNode next; //指向下一个节点 52 53 public HeroNode(int no, String name, String nickname) { 54 this.no = no; 55 this.name = name; 56 this.nickname = nickname; 57 } 58 59 @Override 60 public String toString() { 61 return "HeroNode{" + 62 "no=" + no + 63 ", name='" + name + '\'' + 64 ", nickname='" + nickname + '\'' + 65 '}'; 66 } 67 }
1 /** 2 * 合并两个有序的单链表 使合并完成之后的新的链表依旧有序 3 * @param hero1 4 * @param hero2 5 */ 6 public static HeroNode mergeList(HeroNode hero1, HeroNode hero2){ 7 8 //创建一个新的链表 9 HeroNode hero3 = new HeroNode(0,"",""); 10 11 HeroNode temp1 = hero1.next; 12 HeroNode temp2 = hero2.next; 13 HeroNode temp3 = hero3; 14 15 HeroNode next1 = null;//用于保存下一个节点 16 HeroNode next2 = null; 17 while(temp1!=null&&temp2!=null){ 18 if(temp1.no<temp2.no){ 19 next1 = temp1.next;//先保存下一个节点 20 temp3.next = temp1;//将较小的节点插入到新的节点后面 21 temp3 = temp3.next;//将新的节点后移一位 注意:一定要后移 22 temp1 = next1;//将节点后移一位 23 }else{ 24 next2 = temp2.next; 25 temp3.next = temp2; 26 temp3 = temp3.next; 27 temp2 = next2; 28 } 29 } 30 if(temp1 == null){ 31 while (temp2 !=null){ 32 next2 = temp2.next; 33 temp3.next = temp2; 34 temp3 = temp3.next; 35 temp2 = next2; 36 } 37 }else{ 38 while (temp1!=null){ 39 next1 = temp1.next;//先保存下一个节点 40 temp3.next = temp1;//将较小的节点插入到新的节点后面 41 temp3 = temp3.next;//将新的节点后移一位 注意:一定要后移 42 temp1 = next1;//将节点后移一位 43 } 44 } 45 return hero3; 46 }
1 public static void main(String[] args) { 2 HeroNode heroNode1 = new HeroNode(1,"李1","木子李1"); 3 HeroNode heroNode2 = new HeroNode(2,"李2","木子李2"); 4 HeroNode heroNode3 = new HeroNode(3,"李3","木子李3"); 5 HeroNode heroNode4 = new HeroNode(4,"李4","木子李4"); 6 7 HeroNode heroNode5 = new HeroNode(5,"李5","木子李5"); 8 HeroNode heroNode6 = new HeroNode(6,"李6","木子李6"); 9 HeroNode heroNode7 = new HeroNode(7,"李7","木子李7"); 10 HeroNode heroNode8 = new HeroNode(8,"李8","木子李8"); 11 12 SingleLinkedList list = new SingleLinkedList(); 13 14 list.addOrderByNo(heroNode1); 15 list.addOrderByNo(heroNode3); 16 list.addOrderByNo(heroNode5); 17 list.addOrderByNo(heroNode7); 18 19 SingleLinkedList list2 = new SingleLinkedList(); 20 list2.addOrderByNo(heroNode2); 21 list2.addOrderByNo(heroNode4); 22 list2.addOrderByNo(heroNode6); 23 list2.addOrderByNo(heroNode8); 24 25 //合并两个链表 26 HeroNode heroNode = mergeList(list.getHead(), list2.getHead()); 27 }
原文链接:https://www.cnblogs.com/dong9012/p/13034333.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- Spire.Cloud.SDK for Java 合并、拆分Excel单元格 2020-06-09
- 短短两个月的时间面试了十几次,我终于成为无情的面试机器了 2020-06-04
- 历时两个月,他终于如愿拿到阿里offer了!恭喜恭喜 2020-06-02
- 可见性、原子性和有序性 2020-05-22
- LeetCode 21. 合并两个有序链表 2020-05-22
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash