【剑指offer】面试题25-合并两个排序的链表

题目

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

1.思路

（1）创建一个新链表newlist，尾插法不断将原来的两个链表的结点拼接到其尾部。
（2）当两个链表均不空，同时遍历两个链表，进行元素大小判断，摘下元素值较小的结点尾插到newlist，同时指针后移继续比较。
（3）循环跳出的时候有三种情况
①两个链表都到头了，不需要继续处理；
②list1没到头，newlist.next直接指向list1的剩余结点就好，因为原本就是有序单调递增的；
③list2没到头，newlist.next直接指向list2的剩余结点就好。
（4）返回新的合并后的单调递增的链表

2.代码（Java实现）

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode newlist = new ListNode(10086);
    	ListNode newindex = newlist;
    	ListNode index1 = list1;
    	ListNode index2 = list2;
    	// 两个链表均不空
    	while(list1 != null && list2 != null) {
    		if(list1.val < list2.val) {
    			// list1 比 list2 的元素值小
    			index1 = index1.next;
    			list1.next = newindex.next;
    			newindex.next = list1;
    			newindex = newindex.next;
    			list1 = index1;
    			
    		}else {
    			// list2 比 list1 的元素值小
    			index2 = index2.next;
    			list2.next = newindex.next;
    			newindex.next = list2;
    			newindex = newindex.next;
    			list2 = index2;
    		}
    	}
    	if(list1 != null) {
    		// list1不空
    		newindex.next = list1;
    	}else {
    		// list2不空
    		newindex.next = list2;
    	}
    	return newlist.next;
    }
}

苏州大学计算机考研依然考过这个题，手写代码实现。

本文作者： whtli
本文链接： https://hexo.whtli.cn/archives/2b7e4ff.html
版权声明： 遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。