合併有序兩個單鏈表,合併後鏈表依然有序

最近在學習數據結構,特此記錄一下,方便以後查閱.

 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     }