头插法、尾差法创建单链表及其合并_头插法和尾插法两种方法实现单链表的合并

头插法图示：

尾差法图示：

代码：

package 数据结构;
 
import java.util.Scanner;
/**
 * 带头结点的链表的创建
 * @author wky
 *
 */
class LNode{
	int data;
	LNode next;
}
public class 链表操作 {
	//头插法创建链表
	static LNode create_list_front(int n){
		LNode head,p;
		head = new LNode();
		head.next = null;
		for(int i=0;i<n;i++){
			p = new LNode();
			System.out.println("input elems(list_front):");
			Scanner scn = new Scanner(System.in);
			p.data = scn.nextInt();
			p.next = head.next;
			head.next = p;
		}
		return head;
	}
	
	//尾插法
	static LNode create_list_rear(int n){
		LNode s,r;//s指向新申请的节点，而r指向链表最新的终端节点
		LNode head;
		head = new LNode();
		head.next = null;
		r = head;//r指向head节点，此时head节点就是终端节点
		for(int i=0;i<n;i++){
			s = new LNode();
			System.out.println("input elems(list_rear):");
			Scanner scn = new Scanner(System.in);
			s.data = scn.nextInt();
			r.next = s;//用r来接纳新的节点
			r = r.next;//r指向终端节点
		}
		r.next = null;
		return head;
	}
	//打印链表
	static void print_list(LNode head){
		LNode p;
		p = head.next;
		while(p!=null){
			System.out.print(p.data+",");
			p = p.next;
		}
	}
	
	//两个有序链表合并
	static LNode merge_list(LNode la,LNode lb,LNode lc){
		LNode pa,pb,pc;
		pa = la.next; //pa,pb,pc 相当于一个跟踪标识号。
		pb = lb.next;
		pc = lc;
		while((pa!=null)&&(pb!=null)){
			if(pa.data<=pb.data){
				pc.next = pa;
				pc = pc.next;
				pa = pa.next;
			}else{
				pc.next = pb;
				pc = pc.next;
				pb = pb.next;
			}
		}
		pc.next = null;
		if(pa!=null) pc.next = pa;
		if(pb!=null) pc.next = pb;
		return lc;
	}
	public static void main(String[] args){
		LNode la;
		LNode lb;
		LNode lc;
		lc = new LNode();
		la = create_list_rear(5);
		lb = create_list_rear(6);
		lc = merge_list(la,lb,lc);
		System.out.println("l1:");
		print_list(la);
		System.out.println("l2:");
		print_list(lb);
		System.out.println("l3:");
		print_list(lc);
	}
	
 
}