两个有序链表合并为一个_两个有序链表合成一个有序链表

题目如下：

将两个有序链表合并为一个有序链表，不允许使用额外的内存空间

思路：

（使用java语言）循环实现——>
（1）创建两个链表：链表1和链表2；在合并链表的方法里让链表1的头节点为head1，链表2的头节点为head2
（2）先进行判空，链表1、链表2为空时，执行return；设置两个游标cur1、cur2分别指向两个链表的头节点；设置游标指向的新链表的头newHead和尾newTail
（3）设置while循环，当cur1和cur2指向都不为空时执行循环；
（4）判断cur1和cur2指向的节点的值；cur1小则先判断新链表是否为空；新链表为空就让newHead指向cur1指向的节点，newTail指向cur1指向的节点，cur1向后移动一位；新链表不为空就让newTail.next指向cur1，newTail向后移动一位，cur1向后移动一位；
（5）cur2小则先判断新链表是否为空；新链表为空就让newHead指向cur2指向的节点，newTail指向cur2指向的节点，cur2向后移动一位；新链表不为空就让newTail.next指向cur2，newTail向后移动一位，cur2向后移动一位；
（6）循环终止之后，判断cur1和cur2哪个指向为空，cur1指向为空，就把cur2链接到新链表的尾部；cur2指向为空，就把cur1链接到新链表的尾部；
（7）输出新链表。

思路图示：

代码如下：

public class Test1 {
   

ListNode head = null;
	
	public static void main(String[] args){
   
		Test1 linkList1 = new Test1();//链表1
		Test1 linkList2 = new Test1();//链表2
		linkList1.insert(1);
		linkList1.insert(3);
		linkList1.insert(5);
		linkList1.insert(7);
		linkList1.printLink()
1
2
3
4
5
6
7
8
9
10
11
12
13
14