剑指Offer名企面试题17：合并两个排序的链表（Java实现）

小灰灰 2022-01-05 02:22 120阅读 0赞

> 题目：输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是按照递增排序的。

这道题普通的做法就是：创建一个新的链表，链表的数据分别来自两个排好序的链表，均从链表头部开始遍历，哪个数据小，哪个加入新的链表，当一个表遍历完成，另一个表还有数据，就把另一个表的数据全部加入到新的链表中。 这种做法需要判断边界条件，就是当一个链表遍历完成的时候，如何处理。

这里给出这种算法的代码：

public static LinkedList sort(LinkedList a,LinkedList b){
    	MergeSortedList obj = new MergeSortedList();
    	LinkedList list = obj.new LinkedList();
    	Node p1 = a.head;
    	Node p2 = b.head;
    	while(p1!=null||p2!=null){	
    		if(p1!=null&&p2!=null){	
    			if(p1.data<p2.data){
    				list.insert(p1.data);
    				p1 = p1.next;
    			}else{
    				list.insert(p2.data);
    				p2 = p2.next;
    			}
    		}else if(p1==null){
    			list.insert(p2.data);
    			p2 = p2.next;
    		}else if(p2==null){
    			list.insert(p1.data);
    			p1 = p1.next;
    		}
    	}
    	return list;
    }

这种算法的思路比较直观，但是实现起来，代码量比较大，而且容易出现判断条件书写错误的问题。

另外一种就是使用递归的方法来合并两个链表：

既然每次都是需要找到两个链表中的较小的那个头部元素，可以以这个特征去设计。

1、查找两个链表头部节点a,b中数据较小的节点 min(a,b)，如果a.data<b.data，这个头部元素我们就选择a

2、 继续查找两个链表头部节点a,b中较小的节点，a的头部元素这时候就是a.next ，需要判断的是min(a.next,b)

3、以此类推，直到a.next=null,b.next=null

这个递归的方法，我们需要排序的虽然是两个链表，但是，其实递归的参数是链表的头元素。这么一来，递归的返回值也可以是一个头部元素，我们的算法就可以这么来编码了。

public static Node merge(Node a,Node b){
    	if(a==null){
    		return b;
    	}
    	if(b==null){
    		return a;
    	}
    	if(a.data<b.data){
    		a.next = merge(a.next, b);
    		return a;
    	}else{
    		b.next = merge(a, b.next);
    		return b;
    	}
    }

这个算法，虽然经过实战，但是还是很难理解，到现在我也无法完全理解。算法如果这么来理解，也许还好理解一些，我们不考虑链表，我们考虑的是从两个节点里面找到一个小的节点作为返回值，其实有了这个作为头部节点的返回值，我们就可以知道整个链表了。

最后附上完整的代码，以及运行结果。

package com.xxx.algorithm.sort;
    public class MergeSortedList {
    	class Node{
    		int data;
    		Node next;
    		public Node(int data){
    			this.data = data;
    			this.next = null;
    		}
    	}
    	class LinkedList{
    		Node head;
    		
    		public void insert(int data){
    			if(head==null){
    				head = new Node(data);
    			}else{
    				Node curNode = head;
    				if(data<head.data){
    					Node newNode = new Node(data);
    					head = newNode;
    					head.next = curNode;
    				}else{
    					while(curNode.next!=null){
    						if(data<curNode.next.data){
    							Node next = curNode.next;
    							Node newNode = new Node(data);
    							curNode.next = newNode;
    							newNode.next = next;
    							return;
    						}
    						curNode = curNode.next;
    					}
    					Node newNode = new Node(data);
    					curNode.next = newNode;
    				}	
    			}	
    		}	
    		
    		public void insert2(int data){
    			if(head==null){
    				head = new Node(data);
    			}else{
    				Node curNode = head;
    				while(curNode.next!=null){
    					curNode = curNode.next;
    				}
    				curNode.next = new Node(data);
    			}
    		}
    		
    		public void display(){
    			System.out.print("List:");
    			Node curNode = head;
    			while(curNode!=null){
    				System.out.print(curNode.data+" ");
    				curNode = curNode.next;
    			}
    		}
    		
    		
    	}
    	
    	public static LinkedList sort(LinkedList a,LinkedList b){
    		MergeSortedList obj = new MergeSortedList();
    		LinkedList list = obj.new LinkedList();
    		Node p1 = a.head;
    		Node p2 = b.head;
    		while(p1!=null||p2!=null){	
    			if(p1!=null&&p2!=null){	
    				if(p1.data<p2.data){
    					list.insert(p1.data);
    					p1 = p1.next;
    				}else{
    					list.insert(p2.data);
    					p2 = p2.next;
    				}
    			}else if(p1==null){
    				list.insert(p2.data);
    				p2 = p2.next;
    			}else if(p2==null){
    				list.insert(p1.data);
    				p1 = p1.next;
    			}
    		}
    		return list;
    	}
    	
    	public static Node merge(Node a,Node b){
    		if(a==null){
    			return b;
    		}
    		if(b==null){
    			return a;
    		}
    		if(a.data<b.data){
    			a.next = merge(a.next, b);
    			return a;
    		}else{
    			b.next = merge(a, b.next);
    			return b;
    		}
    	}
    	
    	public static void show(Node head){
    		if(head!=null){
    			System.out.print("List:");
    			while(head!=null){
    				System.out.print(head.data+" ");
    				head = head.next;
    			}
    		}
    	}
    	public static void main(String[] args) {
    		MergeSortedList mergeSortedList = new MergeSortedList();
    		LinkedList list = mergeSortedList.new LinkedList();
    		list.insert(11);
    		list.insert(3);
    		list.insert(5);
    		list.insert(9);
    		list.insert(10);
    		list.insert(8);
    		System.out.println("==list==");
    		list.display();
    		System.out.println();
    		System.out.println("==list2==");
    		LinkedList list2 = mergeSortedList.new LinkedList();
    		list2.insert(4);
    		list2.insert(2);
    		list2.insert(6);
    		list2.insert(13);
    		list2.insert(12);
    		list2.insert(7);
    		list2.display();
    		System.out.println();
    		System.out.println("==ordinary sort==");
    		LinkedList list3 = sort(list, list2);
    		list3.display();
    		System.out.println();
    		System.out.println("==merge sort==");
    		Node head = merge(list.head, list2.head);
    		show(head);
    	}
    }

运行结果：

![20190622194358515.png][]

[20190622194358515.png]: /images/20211230/2e9b5bbc85b84a0b8cd9e9e46c0dd7c5.png