# 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)
# 结点的含义, 不仅表示当前结点对象, 还表示从该结点开始, 直至遍历到next为nil的一条链表.
#
# 头结点, 该头结点本身不是链表的一部分
header = ListNode.new(:header)
# 结果链表
result_list_node = header
loop do
break if l1.nil? or l2.nil?
if l1.val <= l2.val
result_list_node.next = l1
l1 = l1.next
else
result_list_node.next = l2
l2 = l2.next
end
# 光标移位
result_list_node = result_list_node.next
# 截断
result_list_node.next = nil
end
# 剩余片段拼接
result_list_node.next = l1 || l2
# 头结点之后的链表真身
header.next
end