合并排序链表
最近在做一些leetcode上的算法题，有一个合并已排序链表的题很有意思：
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.
最简单的是使用数组保存链表并进行排序，但因运行时间问题在leetcode不能通过，转化为直接操作链表后运行时间缩短到60ms。 代码如下:
# Definition for singly-linked list.
# class ListNode
# attr_accessor :val, :next
# def initialize(val)
# @val = val
# @next = nil
# end
# end
# @param {ListNode} l1
# @param {ListNode} l2
# @return {ListNode}
def merge_two_lists(l1, l2)
#有空链表直接返回另一个链表
return l1 || l2 if !l1 || !l2
#找到两个链表头value最小的节点作为head
if l1.val < l2.val
head = l1
l1 = l1.next
else
head = l2
l2 = l2.next
end
#用temp引用head进行操作
temp = head
#循环到一个链表结束
while l1 && l2
#找到两个链表中value最小的node插入到temp中
if l1.val < l2.val
temp.next = l1
l1 = l1.next
else
temp.next = l2
l2 = l2.next
end
#移动到next
temp = temp.next
end
#将两个链表有剩余的插入到操作中的链表
temp.next = (!l1 ? l2 : l1)
#返回head
head
end