题目

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

翻译

合并两个有序的链表

Hints

Related Topics: LinkedList

参考 归并排序-*，可以递归也可以迭代，基本的链表操作

代码

Java

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) { val = x; }

 * }

 */

class Solution {

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        if(l1==null)    return l2;

        if(l2==null)    return l1;

        if(l1.val<l2.val){

            l1.next = mergeTwoLists(l1.next,l2);

            return l1;

        }else{

            l2.next = mergeTwoLists(l1,l2.next);

            return l2;

        }

    }

}

Python

//recursively

class Solution(object):

    def mergeTwoLists(self, l1, l2):

        if l1==None:    return l2;

        if l2==None:    return l1;

        if l1.val<l2.val:

            l1.next = self.mergeTwoLists(l1.next,l2)

            return l1

        else:

            l2.next = self.mergeTwoLists(l1,l2.next)

            return l2

//iteratively

class Solution(object):

    def mergeTwoLists(self, l1, l2):

        dummy = curr = ListNode(0)

        while l1 and l2:

            if l1.val<l2.val:

                curr.next = l1

                l1 = l1.next

            else:

                curr.next = l2

                l2 = l2.next

            curr = curr.next

        curr.next = l1 or l2

        return dummy.next