it.scala

import scala.annotation.tailrec

@tailrec
def common[T: Ordering](l1: List[T], l2: List[T], accu: List[(T, T)]): List[(T, T)] = {
  (l1, l2) match {
    case (Nil, _) | (_, Nil)  => accu.reverse
    case (h1 :: t1, h2 :: t2) =>
      val cmp = implicitly[Ordering[T]].compare(h1, h2)
      if (cmp < 0) common(t1, l2, accu)
      else if (cmp > 0) common(l1, t2, accu)
      else {
        val i2 = t2.iterator
        val (equaled, rest) = t1.span {_ == i2.next}
        common(rest, i2.toList, (h1, equaled.lastOption.getOrElse(h1)) :: accu)
      }
  }
}


@tailrec
def commonIt[T: Ordering](i1: Iterator[T], i2: Iterator[T], accu: Iterator[(T, T)]): Iterator[(T, T)] = {
  val (bi1, bi2) = (i1.buffered, i2.buffered)
  if (bi1.hasNext && bi2.hasNext) {
    val (h1, h2) = (bi1.head, bi2.head)
    val cmp = implicitly[Ordering[T]].compare(h1, h2)
    if (cmp > 0) {
      bi2.next()
      commonIt(bi1, bi2, accu)
    } else {
      val (equaled, rest) = bi1.span {_ == bi2.next}
      commonIt(rest, bi2, accu ++ Iterator(h1 -> equaled.toList.lastOption.getOrElse(h1)))
    }
  } else accu
}

val l1 = List(2, 3, 4, 8, 9, 12, 14, 17)
val l2 = List(1, 2, 3, 4, 6, 8, 9, 10, 11, 12, 13, 14, 17)
val r1 = common(l1, l2, Nil)
val r2 = commonIt(l1.iterator, l2.iterator, Iterator[(Int, Int)]()).toList
assert(r1 == List((2, 4), (8, 9), (12, 12), (14, 17)))
assert(r2 == List((2, 4), (8, 9), (12, 12), (14, 17)))