面试题 17:合并两个排序的链表

题目:输入两个递增排序的链表,合并这两个链表并使新链表中的结点仍然是按 照递增排序的。

两个指针指向两个链表的头结点，取其中值小的作为新链表的头结点，和之前的结点串联，如此递归。

注意用例：

两个链表都为null；

其中一个链表为null；

两个链表有多个结点，有相同的值，不同的值。

package offer;/*面试题 17:合并两个排序的链表题目:输入两个递增排序的链表,合并这两个链表并使新链表中的结点仍然是按 照递增排序的。*/public class Problem17 {    static class ListNode {        int data;        ListNode nextNode;    }    public static void main(String[] args) {        ListNode head1 = new ListNode();        ListNode second1 = new ListNode();        ListNode head2 = new ListNode();        ListNode second2 = new ListNode();        ListNode third2 = new ListNode();        head1.nextNode = second1;        head2.nextNode = second2;        second2.nextNode = third2;        head1.data = 1;        second1.data = 3;        head2.data = 2;        second2.data = 2;        third2.data = 2;        Problem17 test = new Problem17();        ListNode result = test.mergeList(head1, head2);        System.out.println(result.nextNode.nextNode.nextNode.nextNode.data);    }    public ListNode mergeList(ListNode head1, ListNode head2) {        if (head1 == null) {            return head2;        } else if (head2 == null) {            return head1;        }        ListNode mergeHead = null;        if (head1.data < head2.data) {            mergeHead = head1;            mergeHead.nextNode = mergeList(head1.nextNode, head2);        }else{            mergeHead = head2;            mergeHead.nextNode = mergeList(head1, head2.nextNode);        }        return mergeHead;    }}