如何合并两个有序链表（以O(n)的时间复杂度并且不开辟新的空间）_合并两个有序链表不申请额外空间

这个算法的最重要的思想是，只需要遍历一个链表即可，每次再合适的位置往便利的链表中插入第二个链表的值。

下面就来说一下算法实现原理：

1、遍历第一个链表。

2、因为链表有序，所以只需将第二个链表中的值一个一个插入进去，一遍循环就能完成。

3、特别需要注意头节点插入和第二个链表遍历完的情况。

算法的具体实现：

package classLearn;
 
public class SortForLink {
 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] arr1 = {1,3,6,8,23,34,56,77,90};
		int[] arr2 = {-90,34,55,79,87,98,123,234,567};
		
		Node link1 = new Node();
		Node link2 = new Node();
		Node link3 = new Node();
		
		getLink(arr1,link1);
		getLink(arr2,link2);
		
		mergeLink(link1, link2, link3);
		
		viewLink(link3);
		
		
 
	}
	
	/**
	 * 构建链表
	 * @param arr
	 * @param link
	 */
	public static void getLink(int[] arr, Node link) {
		
		for(int i = 0; i < arr.length; i++) {
			link.setNumber(arr[i]);
			link.setNext(new Node());
			link = link.getNext();
		}
		
	}
	
	/*