单链表

单链表

链表(LinkedList)介绍

  • 链表是有序的列表
  • 链表是以节点的方式来存储,是链式存储
  • 每个节点包含 data 域， next 域：指向下一个节点.
  • 链表的各个节点不一定是连续存储.
  • 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定
添加（创建）
  • 先创建一个head头节点，作用是表示单链表的头
  • 后面每添加一个节点，就直接加入到链表的最后
遍历
  • 通过一个辅助变量遍历，帮助遍历整个链表
使用带head头的单向链表实现 –水浒英雄排行榜管理
  • 完成对英雄人物的增删改查操作， 注: 删除和修改,查找
  • 第一种方法在添加英雄时，直接添加到链表的尾部
  • 第二种方式在添加英雄时，根据排名将英雄插入到指定位置
    (如果有这个排名，则添加失败，并给出提示)
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
//第一种方式
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        //先创建节点
        HeroNode hero1=new HeroNode(1,"宋江","及时雨");
        HeroNode hero2=new HeroNode(2,"卢俊义","玉麒麟");
        HeroNode hero3=new HeroNode(3,"吴用","智多星");
        HeroNode hero4 = new HeroNode(4,"林冲","豹子头");
        //创建链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.add(hero1);
        singleLinkedList.add(hero2);
        singleLinkedList.add(hero3);
        singleLinkedList.add(hero4);
        singleLinkedList.list();
    }
}

//定义SingleLinkedList来管理英雄
class SingleLinkedList{
    //先初始化一个头节点，头结点不要动,不存放具体的数据
    private HeroNode head=new HeroNode(0,"","");

    //添加节点到单向链表
    //思路，当不考虑编号顺序时
    //1、找到当前链表的最后节点
    //2、将最后这个节点的next指向新的节点
    public void add(HeroNode heroNode) {
        //因为head节点不能动，因此我们需要一个辅助变量temp
        HeroNode temp=head;
        //遍历链表，找到最后
        while(true) {
            //找到链表的最后
            if (temp.next==null) {
                break;
            }
            //如果没有找到最后，就将temp后移
            temp=temp.next;
        }
        //当退出while循环时，temp就指向了链表的最后
        //将最后这个节点的next，指向新的节点
        temp.next=heroNode;
    }
    //显示链表【遍历】
    public void list() {
        if (head.next==null) {
            System.out.println("链表为空");
            return;
        }
        //因为头节点不能动，因此需要一个辅助变量来遍历
        HeroNode temp=head.next;
        while(true) {
            //判断是否到链表最后
            if (temp==null) {
                break;
            }
            //输出节点的信息
            System.out.println(temp);
            //将temp后移
            temp=temp.next;
        }
    }
}

//定义HeroNode,每个HeroNode对象就是一个节点
class HeroNode{
    public int no;
    public String name;
    public String nickname;
    public HeroNode next;//指向下一个节点
    //构造器
    public HeroNode(int no,String name,String nickname) {
        this.no=no;
        this.name=name;
        this.nickname=nickname;
    }
    //为了显示方法，我们重写toString
    @Override
    public String toString() {
        return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname+ "]";
    }
}
需要按照编号的顺序添加
  • 首先找到新添加的节点的位置，通过遍历
  • 新的节点.next=temp.next
  • 让temp.next=新的节点
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
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        //先创建节点
        HeroNode hero1=new HeroNode(1,"宋江","及时雨");
        HeroNode hero2=new HeroNode(2,"卢俊义","玉麒麟");
        HeroNode hero3=new HeroNode(3,"吴用","智多星");
        HeroNode hero4 = new HeroNode(4,"林冲","豹子头");
        //创建链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
//        singleLinkedList.add(hero1);
//        singleLinkedList.add(hero2);
//        singleLinkedList.add(hero3);
//        singleLinkedList.add(hero4);

        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero3);
        singleLinkedList.list();
    }
}

//定义SingleLinkedList来管理英雄
class SingleLinkedList{
    //先初始化一个头节点，头结点不要动,不存放具体的数据
    private HeroNode head=new HeroNode(0,"","");

    //添加节点到单向链表
    //思路，当不考虑编号顺序时
    //1、找到当前链表的最后节点
    //2、将最后这个节点的next指向新的节点
    public void add(HeroNode heroNode) {
        //因为head节点不能动，因此我们需要一个辅助变量temp
        HeroNode temp=head;
        //遍历链表，找到最后
        while(true) {
            //找到链表的最后
            if (temp.next==null) {
                break;
            }
            //如果没有找到最后，就将temp后移
            temp=temp.next;
        }
        //当退出while循环时，temp就指向了链表的最后
        //将最后这个节点的next，指向新的节点
        temp.next=heroNode;
    }

    public void addByOrder(HeroNode heroNode) {
        //因为头节点不能动，因此我们通过一个辅助变量来帮助找到添加的位置
        //因为是单链表，我们找的temp是位于添加位置的前一个节点，否则不能插入
        HeroNode temp=head;
        boolean flag=false;//标识添加的编号是否存在，默认为false
        while(true) {
            if (temp.next==null) {//说明temp已经在链表的最后
                break;
            }
            if (temp.next.no>heroNode.no) {//位置找到，就在temp的后面插入
                break;
            }else if(temp.next.no==heroNode.no) {//说明希望添加的heroNode的编号已存在
                flag=true;//说明编号存在
                break;
            }
            temp=temp.next;//后移，遍历当前链表
        }
        //判断flag值
        if (flag) {//不能添加，说明编号存在
            System.out.printf("准备插入的英雄的编号%d已经存在,不能添加\n",heroNode.no);
        }else {
            //添加到链表中,temp的后面
            heroNode.next=temp.next;
            temp.next=heroNode;
        }
    }


    //显示链表【遍历】
    public void list() {
        if (head.next==null) {
            System.out.println("链表为空");
            return;
        }
        //因为头节点不能动，因此需要一个辅助变量来遍历
        HeroNode temp=head.next;
        while(true) {
            //判断是否到链表最后
            if (temp==null) {
                break;
            }
            //输出节点的信息
            System.out.println(temp);
            //将temp后移
            temp=temp.next;
        }
    }
}

//定义HeroNode,每个HeroNode对象就是一个节点
class HeroNode{
    public int no;
    public String name;
    public String nickname;
    public HeroNode next;//指向下一个节点
    //构造器
    public HeroNode(int no,String name,String nickname) {
        this.no=no;
        this.name=name;
        this.nickname=nickname;
    }
    //为了显示方法，我们重写toString
    @Override
    public String toString() {
        return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname+ "]";
    }
}
修改节点
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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        //先创建节点
        HeroNode hero1=new HeroNode(1,"宋江","及时雨");
        HeroNode hero2=new HeroNode(2,"卢俊义","玉麒麟");
        HeroNode hero3=new HeroNode(3,"吴用","智多星");
        HeroNode hero4 = new HeroNode(4,"林冲","豹子头");
        //创建链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
//        singleLinkedList.add(hero1);
//        singleLinkedList.add(hero2);
//        singleLinkedList.add(hero3);
//        singleLinkedList.add(hero4);

        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero3);
        System.out.println("修改前~~~");
        singleLinkedList.list();

        //测试修改节点的代码
        HeroNode newHeroNode=new HeroNode(2, "小贾", "小贾嗯嗯");
        singleLinkedList.update(newHeroNode);
        System.out.println("修改后~~~");
        singleLinkedList.list();
    }
}

//定义SingleLinkedList来管理英雄
class SingleLinkedList{
    //先初始化一个头节点，头结点不要动,不存放具体的数据
    private HeroNode head=new HeroNode(0,"","");

    //添加节点到单向链表
    //思路，当不考虑编号顺序时
    //1、找到当前链表的最后节点
    //2、将最后这个节点的next指向新的节点
    public void add(HeroNode heroNode) {
        //因为head节点不能动，因此我们需要一个辅助变量temp
        HeroNode temp=head;
        //遍历链表，找到最后
        while(true) {
            //找到链表的最后
            if (temp.next==null) {
                break;
            }
            //如果没有找到最后，就将temp后移
            temp=temp.next;
        }
        //当退出while循环时，temp就指向了链表的最后
        //将最后这个节点的next，指向新的节点
        temp.next=heroNode;
    }

    public void addByOrder(HeroNode heroNode) {
        //因为头节点不能动，因此我们通过一个辅助变量来帮助找到添加的位置
        //因为是单链表，我们找的temp是位于添加位置的前一个节点，否则不能插入
        HeroNode temp=head;
        boolean flag=false;//标识添加的编号是否存在，默认为false
        while(true) {
            if (temp.next==null) {//说明temp已经在链表的最后
                break;
            }
            if (temp.next.no>heroNode.no) {//位置找到，就在temp的后面插入
                break;
            }else if(temp.next.no==heroNode.no) {//说明希望添加的heroNode的编号已存在
                flag=true;//说明编号存在
                break;
            }
            temp=temp.next;//后移，遍历当前链表
        }
        //判断flag值
        if (flag) {//不能添加，说明编号存在
            System.out.printf("准备插入的英雄的编号%d已经存在,不能添加\n",heroNode.no);
        }else {
            //添加到链表中,temp的后面
            heroNode.next=temp.next;
            temp.next=heroNode;
        }
    }

    //修改节点的信息，根据no编号来修改，即no编号不能改
    //1、根据newHreoNode的no来修改即可
    public void update(HeroNode newHeroNode) {
        //判断是否为空
        if (head.next==null) {
            System.out.println("链表为空~~~");
            return;
        }
        //找到需要修改的节点，根据no编号
        //定义一个辅助变量
        HeroNode temp=head.next;
        boolean flag=false;//表示是否找到该节点
        while(true) {
            if (temp==null) {
                break;//已经遍历完毕
            }
            if (temp.no==newHeroNode.no) {
                flag=true;
                break;
            }
            temp=temp.next;
        }
        //根据flag判断是否找到要修改的节点
        if (flag) {
            temp.name=newHeroNode.name;
            temp.nickname=newHeroNode.nickname;
        }else {//没有找到
            System.out.printf("没有找到编号%d的节点，不能修改\n",newHeroNode.no);
        }
    }

    //显示链表【遍历】
    public void list() {
        if (head.next==null) {
            System.out.println("链表为空");
            return;
        }
        //因为头节点不能动，因此需要一个辅助变量来遍历
        HeroNode temp=head.next;
        while(true) {
            //判断是否到链表最后
            if (temp==null) {
                break;
            }
            //输出节点的信息
            System.out.println(temp);
            //将temp后移
            temp=temp.next;
        }
    }
}

//定义HeroNode,每个HeroNode对象就是一个节点
class HeroNode{
    public int no;
    public String name;
    public String nickname;
    public HeroNode next;//指向下一个节点
    //构造器
    public HeroNode(int no,String name,String nickname) {
        this.no=no;
        this.name=name;
        this.nickname=nickname;
    }
    //为了显示方法，我们重写toString
    @Override
    public String toString() {
        return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname+ "]";
    }
}
从单链表中删除一个节点
  • 先找到需要删除的这个节点的前一个节点temp
  • temp.next=temp.next.next
  • 被删除的节点，将不会有其他引用指向，会被垃圾回收机制回收
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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        //先创建节点
        HeroNode hero1=new HeroNode(1,"宋江","及时雨");
        HeroNode hero2=new HeroNode(2,"卢俊义","玉麒麟");
        HeroNode hero3=new HeroNode(3,"吴用","智多星");
        HeroNode hero4 = new HeroNode(4,"林冲","豹子头");
        //创建链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
//        singleLinkedList.add(hero1);
//        singleLinkedList.add(hero2);
//        singleLinkedList.add(hero3);
//        singleLinkedList.add(hero4);

        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero3);
        System.out.println("修改前~~~");
        singleLinkedList.list();

        //测试修改节点的代码
        HeroNode newHeroNode=new HeroNode(2, "小贾", "小贾嗯嗯");
        singleLinkedList.update(newHeroNode);
        System.out.println("修改后~~~");
        singleLinkedList.list();

        //删除一个节点
        singleLinkedList.del(2);
        System.out.println("删除后~~~");
        singleLinkedList.list();
    }
}

//定义SingleLinkedList来管理英雄
class SingleLinkedList{
    //先初始化一个头节点，头结点不要动,不存放具体的数据
    private HeroNode head=new HeroNode(0,"","");

    //添加节点到单向链表
    //思路，当不考虑编号顺序时
    //1、找到当前链表的最后节点
    //2、将最后这个节点的next指向新的节点
    public void add(HeroNode heroNode) {
        //因为head节点不能动，因此我们需要一个辅助变量temp
        HeroNode temp=head;
        //遍历链表，找到最后
        while(true) {
            //找到链表的最后
            if (temp.next==null) {
                break;
            }
            //如果没有找到最后，就将temp后移
            temp=temp.next;
        }
        //当退出while循环时，temp就指向了链表的最后
        //将最后这个节点的next，指向新的节点
        temp.next=heroNode;
    }

    public void addByOrder(HeroNode heroNode) {
        //因为头节点不能动，因此我们通过一个辅助变量来帮助找到添加的位置
        //因为是单链表，我们找的temp是位于添加位置的前一个节点，否则不能插入
        HeroNode temp=head;
        boolean flag=false;//标识添加的编号是否存在，默认为false
        while(true) {
            if (temp.next==null) {//说明temp已经在链表的最后
                break;
            }
            if (temp.next.no>heroNode.no) {//位置找到，就在temp的后面插入
                break;
            }else if(temp.next.no==heroNode.no) {//说明希望添加的heroNode的编号已存在
                flag=true;//说明编号存在
                break;
            }
            temp=temp.next;//后移，遍历当前链表
        }
        //判断flag值
        if (flag) {//不能添加，说明编号存在
            System.out.printf("准备插入的英雄的编号%d已经存在,不能添加\n",heroNode.no);
        }else {
            //添加到链表中,temp的后面
            heroNode.next=temp.next;
            temp.next=heroNode;
        }
    }

    //修改节点的信息，根据no编号来修改，即no编号不能改
    //1、根据newHreoNode的no来修改即可
    public void update(HeroNode newHeroNode) {
        //判断是否为空
        if (head.next==null) {
            System.out.println("链表为空~~~");
            return;
        }
        //找到需要修改的节点，根据no编号
        //定义一个辅助变量
        HeroNode temp=head.next;
        boolean flag=false;//表示是否找到该节点
        while(true) {
            if (temp==null) {
                break;//已经遍历完毕
            }
            if (temp.no==newHeroNode.no) {
                flag=true;
                break;
            }
            temp=temp.next;
        }
        //根据flag判断是否找到要修改的节点
        if (flag) {
            temp.name=newHeroNode.name;
            temp.nickname=newHeroNode.nickname;
        }else {//没有找到
            System.out.printf("没有找到编号%d的节点，不能修改\n",newHeroNode.no);
        }
    }


    //删除节点
    public void del(int no) {
        HeroNode temp=head;
        boolean flag=false;//标识是否找到
        while(true) {
            if (temp.next==null) {//已经到链表最后
                break;
            }
            if (temp.next.no==no) {
                flag=true;//找到了待删除节点的前一个节点temp
                break;
            }
            temp=temp.next;
        }
        if (flag) {//找到
            //可以删除
            temp.next=temp.next.next;
        }else {
            System.out.printf("要删除的%d节点不存在",no);
        }
    }

    //显示链表【遍历】
    public void list() {
        if (head.next==null) {
            System.out.println("链表为空");
            return;
        }
        //因为头节点不能动，因此需要一个辅助变量来遍历
        HeroNode temp=head.next;
        while(true) {
            //判断是否到链表最后
            if (temp==null) {
                break;
            }
            //输出节点的信息
            System.out.println(temp);
            //将temp后移
            temp=temp.next;
        }
    }
}

//定义HeroNode,每个HeroNode对象就是一个节点
class HeroNode{
    public int no;
    public String name;
    public String nickname;
    public HeroNode next;//指向下一个节点
    //构造器
    public HeroNode(int no,String name,String nickname) {
        this.no=no;
        this.name=name;
        this.nickname=nickname;
    }
    //为了显示方法，我们重写toString
    @Override
    public String toString() {
        return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname+ "]";
    }
}
单链表的常见面试题有如下:
  • 求单链表中有效节点的个数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 方法：获取到单链表节点的有效个数（如果带头节点的链表，不统计）
/**
 * 
 * @param head 链表的头节点
 * @return 返回的是有效节点的个数
 */
public static int getLength(HeroNode head) {
    if (head.next == null) {
        return 0;
    }
    int length = 0;
    // 定义一个辅助变量
    HeroNode cur = head.next;
    while (cur != null) {
        length++;
        cur = cur.next;// 遍历
    }
    return length;

}
  • 查找单链表中的倒数第k个结点 【新浪面试题】
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
// 查找单链表中的倒数第k个节点
// 思路：
// 1、编写一个方法接收head节点，同时接收一个index
// 2、index表示倒数第index个节点
// 3、先把链表从头到尾遍历一下，得到链表的总长度 getLength
// 4、得到size后，从链表的第一个开始遍历（size-index）个
// 5、如果找到，返回该节点，否则返回空
public static HeroNode findLastIndexNode(HeroNode head, int index) {
    // 判断如果链表为空，返回null
    if (head.next == null) {
        return null;
    }
    // 第一次遍历得到链表的长度
    int size = getLength(head);
    // 第二次遍历
    // 先做一个index校验
    if (index <= 0 || index > size) {
        return null;
    }
    // 定义一个辅助变量
    HeroNode cur = head.next;
    for (int i = 0; i < size - index; i++) {
        cur = cur.next;
    }
    return cur;
}
  • 单链表的反转【腾讯面试题】
    • 先定义一个新的链表reverseHead=new HeroNode();
    • 从头到尾遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表的reverseHead的最前端
    • 原来的链表的head.next=reverseHead.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 将单链表进行反转
public static void reverseList(HeroNode head) {
    // 如果当前链表为空，或者只有一个节点，无需反转，直接返回
    if (head.next == null || head.next.next == null) {
        return;
    }

    HeroNode cur = head.next;// 定义一个辅助变量，用来遍历原来的链表
    HeroNode next = null;// 指向当前节点的下一个节点
    HeroNode reverseHead = new HeroNode(0, "", "");
    // 遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表的reverseHead的最前端
    while (cur != null) {
        next = cur.next;// 先暂时保存当前节点的下一个节点，后面需要使用
        cur.next = reverseHead.next;// 将cur的下一个节点指向新的链表的最前端
        reverseHead.next=cur;//将cur连接到新的链表上
        cur = next;// 让cur指向下一个节点
    }
    // 将head.next指向reverseHead.next，实现单链表的反转
    head.next = reverseHead.next;
}
  • 从尾到头打印单链表 【百度，要求方式1：反向遍历 。 方式2：Stack栈】
    • 方式一：先将单链表进行反转操作，然后遍历即可，这样做的问题是会破坏原来的单链表的结构，不建议
    • 方式二：可以利用栈数据结构，将各个节点压入到栈中，利用栈的先进后出的特点，就可以实现逆序打印的效果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//使用栈实现逆序打印单链表
public static void reversePrint(HeroNode head) {
    if (head.next==null) {
        return;//空链表
    }
    //创建一个栈，将各个节点压入栈
    Stack<HeroNode> stack = new Stack<HeroNode>();
    HeroNode cur=head.next;
    //将链表的所有节点压入栈中
    while(cur!=null) {
        stack.push(cur);
        cur=cur.next;
    }
    //将栈中的节点进行打印，pop出栈
    while(stack.size()>0) {
        System.out.println(stack.pop());
    }
}
  • 合并两个有序的单链表，合并之后的链表依然有序
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
    //合并两个有序链表
public static void mergeLinkedList(HeroNode head1, HeroNode head2) {
    if (head1.next == null || head2.next == null) {
        return;
    }
    HeroNode newHead = new HeroNode(-1, "", "");
    HeroNode cur1 = head1.next;
    HeroNode cur2 = head2.next;
    System.out.println(newHead);
    while (cur1 != null && cur2 != null) {
        if (cur1.no <= cur2.no) {
            newHead.next = cur1;
            newHead = cur1;
            cur1 = cur1.next;
        } else {
            newHead.next = cur2;
            newHead = cur2;
            cur2 = cur2.next;
        }
    }
    if (cur1 == null) {
        newHead.next = cur2;
    } else if (cur2 == null) {
        newHead.next = cur1;
    }
}