链接:https://leetcode.com/problems/merge-two-sorted-lists/#/description
难度:Easy
题目:21. Merge Two Sorted Lists
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.
翻译:合并两个排好序的链列,并将其作为新链表返回。新链表应通过将前两个列表的节点拼接在一起。
思路一:新建一个头指针指向0的临时链表,比较l1和l2的当前值的大小,把临时链表的next节点指向较小的节点,l1或者l2的指针后移一位,依次往下,直到l1或者l2为空,则把临时链表的next节点指向最后那段非空的链表,返回临时链表的第二个节点(头一个节点为0)。
参考代码一(Java)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode newList = new ListNode(0);
        ListNode nextList = newList;

        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                nextList.next = l1;
                l1 = l1.next;
            }else{
                nextList.next = l2;
                l2 = l2.next;
            }
            nextList = nextList.next;
        }

        if(l1 != null){
            nextList.next = l1;
        }else{
            nextList.next = l2;
        }

        return newList.next;

    }
}

思路二:使用递归法。构造一个临时链表,当l1当前节点的值大于l2当前节点的值时,我们把l2这个较小的值赋给临时链表的下一个节点,并将l2的下一个节点的值和l1当前节点的值放到下一次做对比,依次递归下去。
参考代码二(Java)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val > l2.val) {
            ListNode tmp = l2;
            tmp.next = mergeTwoLists(l1, l2.next);
            return tmp;
        } else {
            ListNode tmp = l1;
            tmp.next = mergeTwoLists(l1.next, l2);
            return tmp;
        }
    }
}

互联网校招面试必备——Redis

Redis有哪些数据结构? 字符串String、字典Hash、列表List、集合Set、有序集合SortedSet。 如果你是Redis中高级用户,还需要加上下面几种数据结构HyperLogLog...

阅读全文

互联网校招面试必备——数据库

DDL(Data Definition Language)数据库定义语言 CREATE、ALTER、DROP、TRUNCATE、COMMENT、RENAME DML(Data Manipulation Language)数据操纵语言 SELECT、...

阅读全文

一文搞定BAT面试——Java 集合类

1. Iterator接口 Iterator接口,这是一个用于遍历集合中元素的接口,主要包含hashNext(),next(),remove()三种方法。它的一个子接口LinkedIterator在它的基...

阅读全文