合并两个排序的链表

题目描述

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

思路

1.仿照归并排序中merge的逻辑即可。

Java代码实现

    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode p = new ListNode(-1);
        ListNode res = p;
        while(list1 != null || list2 != null){
            int cur1 = list1 == null ? Integer.MAX_VALUE : list1.val;
            int cur2 = list2 == null ? Integer.MAX_VALUE : list2.val;
            if(cur1 < cur2){
                p.next = new ListNode(cur1);
                list1 = list1.next;
            }else{
                p.next = new ListNode(cur2);
                list2 = list2.next;
            }
            p = p.next;
        }
        return res.next;
    }

Golang代码实现

func Merge(list1 *ListNode,list2 *ListNode)*ListNode{
    res := new(ListNode)
    p := res

    for list1 != nil || list2 != nil {
        if list1 == nil{
            p.Next = &ListNode{list2.Val,nil}
            list2 = list2.Next
            p = p.Next
            continue
        }

        if list2 == nil{
            p.Next = &ListNode{list1.Val,nil}
            list1 = list1.Next
            p = p.Next
            continue
        }

        cur1 := list1.Val
        cur2 := list2.Val

        if cur1<cur2{
            p.Next = &ListNode{cur1,nil}
            list1 = list1.Next
        }else{
            p.Next = &ListNode{cur2,nil}
            list2 = list2.Next
        }
    }
    return res.Next
}