LeetCode 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.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

 

两个链表，连起来按从小到大连起来

看上去比较简单直接，但是没看清题目里已经说了是两个已经排好序的链表，直接的方法定义一个ArrayList，将所有元素添加进去，排序，然后遍历排序后的列表，一个一个写到链表里

Java源码

package com.maoxiaomeng;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author lihui
 * @date 2018/3/26 12:31
 */


class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
    }
}

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        List<Integer> myList = new ArrayList<Integer>();
        while (l1 != null) {
            myList.add(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            myList.add(l2.val);
            l2 = l2.next;
        }
        Collections.sort(myList);
        System.out.println(myList);
        
        ListNode current = new ListNode(myList.get(0));
        ListNode head = current;
        for (int i = 1; i < myList.size(); i++) {
            current.next = new ListNode(myList.get(i));
            current.next = current.next.next;
        }
        return head.next;
    }
}

结果超时了，才发现是两个已经排好序的链表

那么可以两个链表持续比较，反正是排序好的，current指针一直指向当前小的，然后current = current.next

package com.maoxiaomeng;

/**
 * @author lihui
 * @date 2018/3/26 12:31
 */


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;
        }
        ListNode current = new ListNode(0);
        ListNode head = current;
        /**
         * l1: 0->2->4->6
         * l2: 1->3->5->7
         * l : 0->1->2->3->4->5->6->7
         */
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }
        if (l1 != null) {
            current.next = l1;
        }
        if (l2 != null) {
            current.next = l2;
        }
        return head.next;
    }
}

是从current.next开始的，因此返回head.next，这样就OK了

看了下别人提交的Solution，递归的解法，挺难想的

package com.maoxiaomeng;

/**
 * @author lihui
 * @date 2018/3/26 12:31
 */


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;
        }
        /**
         * l1: 0->2->4->6
         * l2: 1->3->5->7
         * l : 0->1->2->3->4->5->6->7
         */
        if (l1.val <= l2.val) {
            ListNode head = l1;
            head.next = mergeTwoLists(l1.next, l2);
            return head;
        } else {
            ListNode head = l2;
            head.next = mergeTwoLists(l1, l2.next);
            return head;
        }
    }
}

还有个C++的解法，连变量都省了，移植到Java也是OK的，反正我是没绕出来

package com.maoxiaomeng;

/**
 * @author lihui
 * @date 2018/3/26 12:31
 */


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;
        }
        /**
         * l1: 0->2->4->6
         * l2: 1->3->5->7
         * l : 0->1->2->3->4->5->6->7
         */
        if (l1.val <= l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

像大脑洞的人学习