合并两个有序链表（Java递归实现）

public class Test17_MergeList { public static void main(String[] args) { //创建链表1 Node head1 = new Node(0); System.out.print("====链表1=====\n"+head1.value+" "); Node[] p1 = new Node[5]; int i = 0, k=0; for(i = 0; k<4; i=i+2,k++){ p1[k] = new Node(i+2); System.out.print(p1[k].value+" "); if(i >= 2){ p1[k-1].next = p1[k]; }else{ head1.next = p1[k]; } } //创建链表2 Node head2 = new Node(1); System.out.print("\n====链表2=====\n"+head2.value+" "); Node[] p2 = new Node[5]; int j = 1, m=0; for(j = 1; m<4; j=j+2,m++){ p2[m] = new Node(j+2); System.out.print(p2[m].value+" "); if(j >= 3){ p2[m-1].next = p2[m]; }else{ head2.next = p2[m]; } } //合并两个有序链表 Node headNode = mergeList(head1, head2); //打印合并后的链表 System.out.println("\n=======合并后的链表========="); while(headNode != null){ System.out.print(headNode.value+" "); headNode = headNode.next; } } private static Node mergeList(Node head1, Node head2) { Node head = null; if(head1 == null){ return head2; }else if(head2 == null){ return head1; } if(head1.value < head2.value){ head = head1; head.next = mergeList(head1.next, head2); }else{ head = head2; head.next = mergeList(head1, head2.next); } return head; } } 输出结果 ====链表1===== 0 2 4 6 8 ====链表2===== 1 3 5 7 9 =======合并后的链表========= 0 1 2 3 4 5 6 7 8 9