【剑指Offer 17】合并两个排序的链表

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

解法1：使用递归

代码：

package demo;

public class Test17 {
    public static class ListNode {
        int value;
        ListNode next;
    }

    /**
     * 递归
     * @param head1
     * @param head2
     * @return
     */
    public static ListNode merge(ListNode head1, ListNode head2) {
        if(head1 == null) {
            return head2;
        } else if(head2 == null) {
            return head1;
        }
    
        // 创建一个临时结点
        ListNode tmp = null;
        if(head1.value < head2.value) {
            tmp = head1;
            tmp.next = merge(head1.next, head2);
        } else {
            tmp = head2;
            tmp.next = merge(head1, head2.next);
        }
        return tmp;
    }

    public static void printList(ListNode head) {
        while(head != null) {
            System.out.print(head.value + "->");
            head = head.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        ListNode head1 = new ListNode();
        head1.value = 1;
        head1.next = new ListNode();
        head1.next.value = 3;
        head1.next.next = new ListNode();
        head1.next.next.value = 4;
        head1.next.next.next = new ListNode();
        head1.next.next.next.value = 7;
        ListNode head2 = new ListNode();
        head2.value = 2;
        head2.next = new ListNode();
        head2.next.value = 4;
        head2.next.next = new ListNode();
        head2.next.next.value = 6;
        head2.next.next.next = new ListNode();
        head2.next.next.next.value = 8;
        ListNode head = new ListNode();
        head = merge(head1, head2);
        printList(head);
    }
}

解法2：使用循环

代码如下：

package demo;

public class Test17 {
    public static class ListNode {
        int value;
        ListNode next;
    }

    /**
     * 使用循环
     * @param head1
     * @param head2
     * @return
     */
    public static ListNode merge(ListNode head1, ListNode head2) {
        if(head1 == null) {
            return head2;
        } else if(head2 == null) {
            return head1;
        }

        // 创建一个当前处理结点
        ListNode curr = new ListNode();
        // 创建一个临时结点，存放当前处理结点即合并后的头结点
        ListNode tmp = curr;
        while(head1 != null && head2 != null) {
            if(head1.value < head2.value) {
                curr.next = head1;
                head1 = head1.next;
            } else {
                curr.next = head2;
                head2 = head2.next;
            }
            curr = curr.next;
        }
    
        if(head1 != null) {
            curr.next = head1;
        }
        if(head2 != null) {
            curr.next = head2;
        }
        
        return tmp.next;
    }

    public static void printList(ListNode head) {
        while(head != null) {
            System.out.print(head.value + "->");
            head = head.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        ListNode head1 = new ListNode();
        head1.value = 1;
        head1.next = new ListNode();
        head1.next.value = 3;
        head1.next.next = new ListNode();
        head1.next.next.value = 4;
        head1.next.next.next = new ListNode();
        head1.next.next.next.value = 7;
        ListNode head2 = new ListNode();
        head2.value = 2;
        head2.next = new ListNode();
        head2.next.value = 4;
        head2.next.next = new ListNode();
        head2.next.next.value = 6;
        head2.next.next.next = new ListNode();
        head2.next.next.next.value = 8;
        ListNode head = new ListNode();
        head = merge(head1, head2);
        printList(head);
    }
}

来源：http://blog.csdn.net/derrantcm/article/details/46678155