LeetCode 21:Merge Two Sorted Lists

作者: LiHui 分类: LeetCode 发布时间: 2018-04-12 22:52

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;
}
}
}

像大脑洞的人学习

纯属恶搞

浙ICP备16024533号

浙公网安备 33010802007459号