特点:
1 //定义一个HeroNode类,每一个HeroNode类的对象都是要给节点,包含对象的属性以及下一个节点的地址 2 class HeroNode{ 3 //data域 4 public int id; 5 public String name; 6 public String address; 7 8 //创建构造器,用于初始化每个节点中的data域,即为英雄的属性赋值 9 public HeroNode(int id,String name,String address) { 10 this.id = id; 11 this.name = name; 12 this.address = address; 13 } 14 15 //next域,指向下一个节点【默认值为null,代表链表的尾部】 16 HeroNode next; 17 18 //重写toString方法,使打印节点对象的地址 --> 打印节点对象的内容【只打印每个节点对象中的data域】 19 @Override 20 public String toString() { 21 return "HeroNode [id=" + id + ", name=" + name + ", address=" + address + "]"; 22 } 23 24 }
1 //定义一个SingleLinkedList类,用于管理整个单链表【带头节点的】 2 class SingleLinkedList{ 3 //每个链表对象都会有一个头节点,所以先创建一个头节点对象 4 HeroNode headHeroNode = new HeroNode(0, "", ""); 5 6 //1、直接向单链表的末尾追加节点 7 public void addToLast(HeroNode newHeroNode) { 8 //头节点不能动,借助辅助指针进行遍历 9 HeroNode tmp = headHeroNode; 10 while(true) { 11 if (tmp.next == null) { 12 //说明到了链表的尾部 13 tmp.next = newHeroNode; 14 break; 15 } 16 //向后移动 17 tmp = tmp.next; 18 } 19 } 20 21 //2、按照id号进行顺序【升序】排序 22 // <-- 3 --> 23 //0 1 2 4 5 24 public void addByAscend(HeroNode newHeroNode) { 25 //辅助指针进行遍历,找到带升序的节点 26 HeroNode tmp = headHeroNode; 27 while(true) { 28 if(tmp.next == null) { 29 //追加到链表的末尾 30 tmp.next = newHeroNode; 31 break; 32 } 33 //如果是降序的话此处应改为:newHeroNode.id > tmp.id 34 if (tmp.next.id > newHeroNode.id) { 35 tmp.next = newHeroNode; //与前一个节点建立连接 36 newHeroNode.next = tmp.next; 37 break; 38 } 39 else if(tmp.next.id == newHeroNode.id) { 40 System.out.println("id号为:" + newHeroNode.id + "已存在,不能插入"); 41 break; 42 } 43 tmp = tmp.next; 44 } 45 } 46 47 //3、修改节点【根据id号查找与之对应的节点】 48 //1 -- 3 -- 7 -- 9 49 // 3-->5 50 public void modify(HeroNode modifyNode) { 51 if (headHeroNode.next == null) { 52 System.out.println("链表空,无可修改的数据"); 53 } 54 //定义临时指针代替头节点进行遍历 55 HeroNode tmp = headHeroNode.next; 56 while(true) { 57 if (tmp == null) { 58 System.out.println("修改失败,原因:未查找到id号为:" + modifyNode.id + "的节点"); 59 //记得干掉方法 60 return; 61 } 62 if (tmp.id == modifyNode.id) { 63 String oldName = tmp.name; 64 //其实所谓的修改,就是重新将遍历到的节点中的data域重新赋值 65 tmp.id = modifyNode.id; 66 tmp.name = modifyNode.name; 67 tmp.address = modifyNode.address; 68 System.out.println("英雄" + oldName + "的数据已被成功修改~~~"); 69 break; 70 } 71 //继续遍历 72 tmp = tmp.next; 73 } 74 } 75 76 //4、删除节点 4 77 //1 -- 3 -- 4 -- 5 -- 7 78 public void delete(HeroNode deleteNode) { 79 if(headHeroNode.next == null) { 80 System.out.println("链表为空,无可删除的数据"); 81 return; 82 } 83 //根据传入节点的id号进行遍历查询 84 //同样,头节点不能动,借助辅助指针进行链表的遍历 85 HeroNode tmp = headHeroNode; 86 while(true) { 87 if (tmp == null) { 88 System.out.println("删除失败,原因:并未查找到id号为" + deleteNode.id + "的节点"); 89 return; 90 } 91 if(tmp.next.id == deleteNode.id) { 92 tmp.next = tmp.next.next; 93 System.out.println(deleteNode.name + "已被成功删除"); 94 return; 95 } 96 //继续遍历 97 tmp = tmp.next; 98 } 99 } 100 101 //5、遍历单链表 102 public void list() { 103 if (headHeroNode.next == null) { 104 System.out.println("链表空,无数据"); 105 return; 106 }else { 107 //借助临时指针进行遍历 108 HeroNode tmp = headHeroNode.next; 109 while(tmp != null) { 110 System.out.println(tmp); 111 tmp = tmp.next; 112 } 113 } 114 } 115 116 117 118 //返回单链表的头部 119 public HeroNode head() { 120 return headHeroNode; 121 } 122 123 //常见面试题:--> 1、求链表中有效节点的个数 【valid:有效的】 124 //需要传入一个头节点,因为每个单链表对象都不一样【长度也会有所差异】 125 public int validNodes(HeroNode head) { 126 //链表为空或者只有一个头节点 127 if (head == null || head.next == null) { 128 return 0; 129 } 130 //借助辅助指针进行遍历 131 HeroNode tmp = head.next; 132 int count = 0; //计数器 133 while(tmp != null) { 134 count++; 135 tmp = tmp.next; 136 } 137 return count; 138 } 139 140 //2、新浪面试题:求单链表中倒数第k个节点【reciprocal:倒数】 141 public HeroNode reciprocalNode(HeroNode headNode,int k) { 142 //空链表 143 if(headHeroNode.next == null) { 144 System.out.println("链表空"); 145 return null; 146 } 147 //求出有效节点的个数 148 int validNodes = validNodes(headNode); 149 //k大于链表中有效数字的长度或者为非正整数 150 if (k > validNodes || k <= 0) { 151 System.out.println("k大于链表中有效数字的长度或者为非正整数"); 152 return null; 153 } 154 //正常遍历情况:倒数第k个:即为有效数字的个数 - k 155 int index = validNodes - k; 156 //借助辅助指针进行遍历 157 HeroNode tmp = headNode.next; 158 //定义计数器用于记住遍历了几次 159 int count = 0; 160 while(true) { 161 if (count == index) { 162 return tmp; 163 } 164 count++; 165 tmp = tmp.next; 166 } 167 } 168 169 //3、腾讯面试题:单链表的反转 170 //思路:创建一个新的链表,每遍历到原链表中的一个节点便将其添加到新链表的头节点之后 171 public void reverse(HeroNode headNode) { 172 if (headNode.next == null || headNode.next.next == null) { 173 System.out.println("链表为空或只有一个节点,无需反转"); 174 return; 175 } 176 HeroNode tmp = headNode.next; //临时指针遍历原来的链表 177 HeroNode nextNode = tmp.next; //记住下一个将要被遍历的节点 178 HeroNode reverseHead = new HeroNode(0, "", ""); //反转后的链表头 179 while(true) { 180 if(tmp == null) { 181 break; 182 }else { 183 nextNode = tmp.next; //先记住下个节点 184 tmp.next = reverseHead.next; //与链表头的下一个节点建立连接 185 reverseHead.next = tmp; //与链表头建立连接 186 tmp = nextNode; //遍历下个节点 187 } 188 } 189 //更换链表头,将旧的链表的头部指向新的链表头部后的第一个节点 190 headNode.next = reverseHead.next; 191 } 192 193 //4、百度面试题:从尾到头遍历单链表 194 //方法一:反转链表,打印【缺点:破坏原来链表的结构】 195 //方法二:使用栈,利用栈先进后出的特点,每遍历到一个接待你就将其push到栈中,最后pop所有的节点 196 public void reverseOrderPrint(HeroNode headNode) { 197 if (headNode.next == null) { 198 System.out.println("链表空,无需逆序打印"); 199 return; 200 }else { 201 //定义栈容器 202 Stack<HeroNode> nodes = new Stack<>(); 203 //辅助指针遍历单链表 204 HeroNode tmp = headNode.next; //0 1 2 3 5 6 9 7 205 while(tmp != null) { 206 //压栈 207 nodes.push(tmp); 208 tmp = tmp.next; 209 } 210 int size = nodes.size(); 211 while(size != 0) { 212 System.out.println(nodes.pop()); 213 size--; 214 } 215 } 216 } 217 218 //5、作业:合并两个有序的单链表,合并后仍然是有序的【升序】 219 //思路:依次取出两个单链表中的id值进行比较,将较小值追加到新的链表的后边 220 //如果一个链表已经到了末尾,则直接将另一个链表剩余的节点追加到新的链表的尾部 221 public static HeroNode mergeList(HeroNode head1,HeroNode head2) { 222 //如果两个单链表均为空则返回null 223 if (head1 == null && head2 == null) { 224 System.out.println("两个链表均为空,无需合并"); 225 return null; 226 }else if (head1 == null) { //如果其中一个单链表为空则返回另一个单链表即可 227 return head2; 228 }else if (head2 == null) { 229 return head1; 230 } 231 //两个单链表都不为空 232 //为单链表1定义一个临时指针进行遍历,并记住下一个将要被遍历到的节点 233 HeroNode tmp1 = head1.next; 234 HeroNode next1 = null; 235 //为单链表2定义一个临时指针进行遍历,并记住下一个将要被遍历到的节点 236 HeroNode tmp2 = head2.next; 237 HeroNode next2 = null; 238 //定义合并后的链表头 239 HeroNode mergeHead = new HeroNode(0, "", ""); 240 //同样,新的链表的头节点不能动,借助辅助指针遍历新的链表,用于借助链表遍历到的位置,便于追加节点 241 HeroNode tmpMerge = mergeHead; //此处不能为gergeHead.next,因为新链表的next为空,否则会出现空指针异常 242 while(tmp1 != null && tmp2 != null) { 243 if (tmp1.id < tmp2.id) { //轮到链表1 244 //记住链表1中下一个将要被遍历到的节点 245 next1 = tmp1.next; 246 //链接到新的链表的上 247 tmp1.next = tmpMerge.next; 248 tmpMerge.next = tmp1; 249 //临时指针向后移 250 tmpMerge = tmpMerge.next; 251 //继续遍历 252 tmp1 = next1; 253 } 254 else { //轮到链表2 255 next2 = tmp2.next; 256 tmp2.next = tmpMerge.next; 257 tmpMerge.next = tmp2; 258 //临时指针向后移 259 tmpMerge = tmpMerge.next; 260 tmp2 = next2; 261 } 262 if (tmp1 == null) { 263 //如果链表1为空,则将链表2中剩余的所有节点都链接到新的链表上 264 tmpMerge.next = tmp2; 265 break; 266 }else if(tmp2 == null) { 267 tmpMerge.next = tmp1; 268 break; 269 } 270 } 271 return mergeHead; 272 } 273 274 }
测试类中的部分测试数据:
1 public class SingleLinkedListDemo2 { 2 3 public static void main(String[] args) { 4 System.out.println("测试单链表添加数据:"); 5 HeroNode hero1 = new HeroNode(1, "曹操", "魏国"); 6 HeroNode hero4 = new HeroNode(4, "刘备", "蜀国"); 7 HeroNode hero7 = new HeroNode(7, "诸葛亮", "蜀国"); 8 HeroNode hero9 = new HeroNode(9, "孙权", "吴国"); 9 SingleLinkedList heroList = new SingleLinkedList(); 10 heroList.addToLast(hero1); 11 heroList.addToLast(hero4); 12 heroList.addToLast(hero7); 13 heroList.addToLast(hero9); 14 15 // heroList.addByAscend(hero1); 16 // heroList.addByAscend(hero2); 17 // heroList.addByAscend(hero3); 18 // heroList.addByAscend(hero4); 19 heroList.list(); 20 21 // System.out.println("修改后:--->"); 22 // HeroNode hero5 = new HeroNode(1, "夏侯惇", "魏国"); 23 // heroList.modify(hero5); 24 25 // System.out.println("删除后:--->"); 26 // HeroNode delNode = new HeroNode(1, "曹操", "魏国"); 27 // heroList.delete(delNode); 28 29 // System.out.println("有效节点个数为:" + heroList.validNodes(heroList.head())); 30 31 // System.out.println("倒数第k个节点:-->"); 32 // System.out.println(heroList.reciprocalNode(heroList.headHeroNode, 5)); 33 34 // System.out.println("反转链表后:"); 35 // heroList.reverse(heroList.head()); 36 37 // System.out.println("逆序打印链表:"); 38 // heroList.reverseOrderPrint(heroList.head()); 39 // heroList.list(); 40 System.out.println("-----------------------------"); 41 HeroNode hero2 = new HeroNode(2, "夏侯惇", "魏国"); 42 HeroNode hero5 = new HeroNode(5, "马超", "蜀国"); 43 HeroNode hero8 = new HeroNode(8, "周瑜", "吴国"); 44 HeroNode hero10 = new HeroNode(10, "张飞", "蜀国"); 45 SingleLinkedList heroList2 = new SingleLinkedList(); 46 heroList2.addToLast(hero2); 47 heroList2.addToLast(hero5); 48 heroList2.addToLast(hero8); 49 heroList2.addToLast(hero10); 50 heroList2.list(); 51 System.out.println("合并两个有序的单链表:-->"); 52 HeroNode newHeroHead = SingleLinkedList.mergeList(heroList.head(), heroList2.head()); 53 SingleLinkedList mergeList = new SingleLinkedList(); 54 mergeList.addToLast(newHeroHead.next);//注:去掉头节点插入【不然会出现两个头节点】 55 System.out.println("------------------"); 56 mergeList.list(); 57 } 58 59 }
由于功能较为繁多,之前测试的结果忘记保存了,在此就贴一张最后一个合并两个有序的单链表,合并后依然有序的结果把~