Java实现 将两个有序的链表合并为一个不能使用额外的存储空间_原地进行有序表的合并,不使用额外空间

有序链表的合并 原地操作

public class MergeSortedLinkedList {
	/*
	 *  双指针+从后往前扫描
	 *  可原地操作
	 */
	public static void main(String[] args) {
		//数据源
		Integer [] data1=new Integer[] {2,3,5,7,8};
		Integer [] data2=new Integer[] {1,3,4,6,8,10};
		List<Integer> li1=Arrays.asList(data1);
		List<Integer> li2=Arrays.asList(data2);
		//根据数据源创建两个链表
		LinkedList<Integer> list1=new LinkedList<>(li1);
		LinkedList<Integer> list2=new LinkedList<>(li2);
		for(int size=list2.size(),i=0;i<size;i++)
			list1.add(0);//将链表1的长度初始化为m+n
		//合并
		merge(list1,list2,list1.size()-1,list2.size()-1);
		//展示结果
		System.out.println(list1);
		
	}

	public static void merge(LinkedList<Integer> list1, LinkedList<Integer> list2,int m,int n) {
		/*
		 * 1 定义两个指针分别指向链表的最后
		 * 2 对指针指向的元素进行比较，较大的放在链表1的最后
		 * 3 当其中的一个指针失效时，退出循环。
		 * 4 如果此时另一个指针还有效，将其指向的元素都放到链表1的最前面
		 */
		int len=m;
		Integer num=null,num1=null,num2=null;
		m=m-n-1;
		while(m>=0&&n>=0) {
			num1=list1.get(m);
			num2=list2.get(n);
			num=num1<=num2?num2:num1;
			list1.set(len--, num);
			if(num==num1)
				m--;
			else
				n--;
		}
		//将list2剩余元素放到list1前面
		if(n>=0)
			for(int i=n;i>=0;i--) {
				num=list2.get(i);
				list1.set(i, num);	
			}
	}

}
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

结果