题目
将两个排序链表合并为一个新的排序链表。http://www.lintcode.com/zh-cn/problem/merge-two-sorted-lists/
分析
很基础的题目,把一个链表中的元素逐一取出,插入到另一个链表即可,注意一下头结点的特殊处理就完了。
代码
public class Solution {
ListNode mergeList(ListNode head, ListNode node){
if(head == null) return node;
if(node.val < head.val){
node.next = head;
return node;
}
ListNode pre = head;
for(ListNode current = head.next; current != null && (current.val < node.val); current = current.next){
pre = current;
}
node.next = pre.next;
pre.next = node;
return head;
}
/*
* @param l1: ListNode l1 is the head of the linked list
* @param l2: ListNode l2 is the head of the linked list
* @return: ListNode head of linked list
*/
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// write your code here
for(; l2 != null ;){
ListNode temp = l2;
l2 = l2.next;
temp.next = null;
l1 = mergeList(l1, temp);
}
return l1;
}
}