题解 | 有序链表合并

题目：已知两个链表list1 和 list2 各自有序，需要爸他们合并成依然有序的链表，结果依然有序且包含两个链表的结点值。

问题分析：

1. 可以通过改变链表结点的指向，重新形成新的链表。需要注意，链表指向移动时，不能丢失链表，所以，需要定义结点指针记录链表。链表是有序的，则：

   第一步：确定哪个链表的第一个结点作为头结点，通过结点值确定。 第二步：依次比较两个链表的结点值，把链表指向比较小的值的结点。 第三步：当一个链表遍历完，则把指针指向剩下链表的结点。

//
class Node{
	int data;
  	Node next = null;
  	public Node(int data){
    	this.data = data;
    }
}

public class ListedList{
	public static Node mergeList(Node list1, Node list2){
    	//判断链表是否为空
      	if(list1.next == null){
        	return list2;
        }
      	if(list2.next == null){
        	return list2;
        }
      	//定义三个结点指针，分别记录链表1，链表2已经头结点
      	Node p1,p2,head;
      	
      	//确定合并后的头结点
      	if(list1.data <= list2.data){
        	head = list1;//头指针指向list1，此时list1的第一个结点作为合并链表的头结点
          	p1 = list1.next;//p1指针指向list1的第二个结点
          	p2 = list2;//p2指向list2
        }else{
        	head = list2.next;//list2作为合并链表的头结点
          	p1 = list1;
          	p2 = list2.next;
        }
      
      	Node team = head;//辅助指针，用来遍历链表
      	while(p1 != null && p2 != null){
        	//通过比较，把链表当前结点添加到合并链表尾部
          	if(p1.data <= p2.data){
            	team.next = p1;//当前结点指向p1指向的结点，即把p1指向的结点插入到合并链表尾部
              	team = p1;//移动辅助指针，指向新插入尾部的结点，这结点将作为下一次比较结点
              	p1 = p1.next;//p1指向下一结点
            }else{
            	team.next = p2; //把链表2的结点插入合并链表尾部，这里说明链表2结点值小于链表1结点值
              	team = p2;
              	p2 = p2.next;
            }
          	//当其中一条链表遍历完，就把指针指向另一条链表还没插入合并链表的结点处，此时，循环也停止，排序完成
          	if(p1 != null){
            	team.next = p1;
            }
          	if(p2 != null){
            	team.next = p2;
            }
        }
      return head;
    }
}