[leetcode]Merge Two Sorted Lists

新博文地址：[leetcode]Merge Two Sorted Lists

http://oj.leetcode.com/problems/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 tw

 归并两个排好序的链表，主要考察最基本的链表操作，其实跟数组的归并排序没啥区别

一般情况下，有两种解法：时间复杂度都是O(m+n)

一种是在原链表的基础上进行连接，空间复杂度O(1)；

另一种是再建一个新的链表以方便存放连接后的结果，空间复杂度为O(m+n)，但是这种操作起来要稍稍简单一点点，主要还是看面试官的要求啦。

不废话：

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
		if (l1 == null || l2 == null) {
			return l1 == null ? l2 : l1;
		}
		ListNode mergeLeft = new ListNode(0);
		ListNode mergeHead = mergeLeft;
		ListNode l1left = l1;
		ListNode l2left = l2;
		while (l1left != null || l2left != null) {
			if (l1left == null) {
				mergeLeft.next = l2left;
				l2left = null;
			} else if (l2left == null) {
				mergeLeft.next = l1left;
				l1left = null;
			} else {
				if (l1left.val < l2left.val) {
					mergeLeft.next = l1left;
					l1left = l1left.next;
				} else {
					mergeLeft.next = l2left;
					l2left = l2left.next;
				}
				mergeLeft = mergeLeft.next;
			}
		}
		return mergeHead.next;
    }

 

评论

2 楼 249326109 2014-06-25  

竟然搜到了你的题目！不过解法TYTS,
http://my.oschina.net/jdflyfly/blog/283992

1 楼 249326109 2014-06-25  

还不赶快还刷题，又跑哪去了