美文网首页
剑指offer:合并两个排序的链表

剑指offer:合并两个排序的链表

作者: 衣介书生 | 来源:发表于2018-04-05 14:58 被阅读3次

    题目分析

    输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。

    代码

    /*
    public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }*/
    public class Solution {
        public ListNode Merge(ListNode list1,ListNode list2) {
            // 两个都为空
            if(list1 == null && list2 == null) {
                return null;
            }
            // 任意一个为空
            if(list1 == null && list2 != null) {
                return list2;
            }
            if(list1 != null && list2 == null) {
                return list1;
            }
            // 定义一个哑结点辅助
            ListNode dummy = new ListNode(0);
            ListNode tail = dummy;
            while(list1 != null && list2 != null) {
                if(list1.val < list2.val) {
                    ListNode temp = list1;
                    list1 = list1.next;
                    temp.next = null;
                    tail.next = temp;
                    tail = temp;
                } else {
                    ListNode temp = list2;
                    list2 = list2.next;
                    temp.next = null;
                    tail.next = temp;
                    tail = temp;
                }
            }
            if(list1 != null) {
                tail.next = list1;
            }
            if(list2 != null) {
                tail.next = list2;
            }
            return dummy.next;
        }
    }
    

    相关文章

      网友评论

          本文标题:剑指offer:合并两个排序的链表

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