美文网首页
【剑指Offer 17】合并两个排序的链表

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

作者: 3e1094b2ef7b | 来源:发表于2017-07-08 22:54 被阅读6次

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

    解法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

    相关文章

      网友评论

          本文标题:【剑指Offer 17】合并两个排序的链表

          本文链接:https://www.haomeiwen.com/subject/vrvjhxtx.html