java数据结构和算法——单链表（Linked List）合并两个单链表，合并之后的链表依然有序_合并两条有序的单向链表,使得合并后的链表也是有序的 (要求: 不能额外申请堆内存

一、合并两个单链表，合并之后的链表依然有序的代码示例

1、定义一个人员节点类，每一个PersonNode对象就是一个节点

package com.rf.springboot01.dataStructure.singleLinkedList2;
/**
 * @description: 定义一个人员节点类，每一个PersonNode对象就是一个节点
 * @author: xiaozhi
 * @create: 2020-07-15 16:44
 */
public class PersonNode {

    public int num;//编号
    public String name;//名称
    public String aliasName;//别名
    public PersonNode next;//指向下一个节点

    //构造器
    public PersonNode(int num, String name, String aliasName) {
        this.num = num;
        this.name = name;
        this.aliasName = aliasName;
    }
    public PersonNode() {

    }

    //重写toString方法
    @Override
    public String toString() {
        return "PersonNode{" +
                "num=" + num +
                ", name='" + name + '\'' +
                ", aliasName='" + aliasName + '\'' +
                '}';
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

2、创建一个单链表管理人员节点

package com.rf.springboot01.dataStructure.singleLinkedList2;
/**
 * @description:
 * @author: xiaozhi
 * @create: 2020-07-21 23:26
 */
public class SingleLinkedList {
    //先初始化一个头结点，头节点位置固定，不存放任何数据，作用是表示链表的头节点
    private PersonNode head;

    public SingleLinkedList(PersonNode head) {
        this.head = head;
    }
    public SingleLinkedList() {
        head = new PersonNode();
    }

    //在链表的指定位置添加节点数据
    public void addByNum(PersonNode personNode) {
        PersonNode temp = head;
        boolean flag = false;//插入的编号是否存在，默认不存在
        while (true) {
            if (temp.next == null) {//已经在链表的尾部
                break;
            }
            if (temp.next.num > personNode.num) {//找到位置，在temp后添加
                break;
            }
            if (temp.next.num == personNode.num) {//编号已经存在，不能添加
                flag = true;
                break;
            }
            temp = temp.next;//后移，遍历
        }
        if (flag) {
            System.out.printf("添加的人员编号%d已经存在，不能添加\n", personNode.num);
        } else {
            //添加数据到链表中，temp后的位置
            personNode.next = temp.next;
            temp.next = personNode;
        }

    }

    //显示链表
    public void show() {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //因为头节点不能动，所以需要一个临时变量来遍历
        PersonNode temp = head.next;
        while (true) {
            //判断是否到链表最后
            if (temp == null) {
                break;
            }
            //输出节点信息
            System.out.println(temp);
            //将temp向后移动
            temp = temp.next;
        }
    }

    /**
     * @Description: 合并两个单链表，合并之后的链表依然有序
     * @Param: head1  head2
     * @Author: xz
     * @return: PersonNode
     * @Date: 2020/7/21 15:50
     */
    public static SingleLinkedList mergeLinkedList(SingleLinkedList list1, SingleLinkedList list2) {
        // 判断需要合并的链表是否为空
        if (list1.head.next == null && list2.head.next == null) {
            throw new RuntimeException("需要合并的两条链表都为空！");
        }
        // 一条链表为空，直接返回另一条链表
        if (list1.head.next == null) {
            System.out.println(list2);
        }
        if (list2.head.next == null) {
            System.out.println(list1);
        }
        //定义合并之后的新链表的头节点
        PersonNode newHead = new PersonNode();
        PersonNode current = newHead; // 定义一个current结点指向新链表
        //定义临时变量
        PersonNode temp1 = list1.head.next;
        PersonNode temp2 = list2.head.next;
        while (temp1 != null && temp2 != null) {
            if (temp1.num < temp2.num) {
                current.next = temp1;
                // 新链表中，current指针的下一个结点对应较小的那个数据
                temp1 = temp1.next;//temp1指针后移
                current = current.next; // current指针后移
            } else {
                current.next = temp2;
                temp2 = temp2.next;
                current = current.next;
            }
        }
        // 合并剩余的元素
        if (temp1 == null) {
            // 说明链表1遍历完了，是空的
            current.next = temp2;
        }
        if (temp2 == null) {
            // 说明链表2遍历完了，是空的
            current.next = temp1;
        }
       return new SingleLinkedList(newHead);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

3、定义一个测试类

package com.rf.springboot01.dataStructure.singleLinkedList2;
/**
 * @description:
 * @author: xiaozhi
 * @create: 2020-07-21 23:28
 */
public class SingleLinkedListTest {
    public static void main(String[] args) {
        //创建节点
        PersonNode personNode1 = new PersonNode(1, "张三", "小张");
        PersonNode personNode2 = new PersonNode(2, "李四", "小李");
        PersonNode personNode3 = new PersonNode(3, "王五", "小王");
        PersonNode personNode4 = new PersonNode(4, "赵二", "小赵");
		//添加链表节点
        SingleLinkedList list1 = new SingleLinkedList();
        list1.addByNum(personNode1);
        list1.addByNum(personNode4);
        System.out.println("添加的第一个链表节点数据如下：============");
        //查询链表所有节点
        list1.show();
        
        //添加链表节点
        SingleLinkedList list2 = new SingleLinkedList();
        list2.addByNum(personNode2);
        list2.addByNum(personNode3);
        System.out.println("添加的第二个链表节点数据如下：============");
        //查询链表所有节点
        list2.show();

        System.out.println("合并后的新链表的节点数据如下：============");
        SingleLinkedList list= SingleLinkedList.mergeLinkedList(list1,list2);
        //查询合并后的链表所有节点
        list.show();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

4、输出结果如下：