LeetCode.合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

• 示例：
  输入：1->2->4, 1->3->4
  输出：1->1->2->3->4->4

解法：一次遍历，O(m+n)

object MergeSortedLinkedList {

     def main(args: Array[String]): Unit = {
          println(solution(
               ListNode(1, ListNode(3, ListNode(5, null))),
               ListNode(2, ListNode(4, null))
          ))
     }

     def solution(first: ListNode, second: ListNode): ListNode = {
          if (first == null) return second
          if (second == null) return first
          var cur = if (first.value > second.value) second else first
          val head = cur
          var i = if (first.value > second.value) first else first.next
          var j = if (first.value > second.value) second.next else second
          while (i != null && j != null) {
               if (i.value > j.value) {
                    cur.next = j
                    j = j.next
               } else {
                    cur.next = i
                    i = i.next
               }
               cur = cur.next
          }
          while (i != null) {
               cur.next = i
               cur = cur.next
               i = i.next
          }

          while (j != null) {
               cur.next = j
               cur = cur.next
               j = j.next
          }

          head
     }

     case class ListNode(value: Int, var next: ListNode)
}