S1, S2 are sorted lists

union(S1,S2)
        P1 := S1
        P2 := S2
        PREV  := new Cell(777, NULL) /* output */
        OUTPUT := PREV
        while P1 <> NULL or P2 <> NULL
           if P1 = NULL then
              PREV.next :=
                new Cell(P2.value, NULL)
              P2 := P2.next
           else if P2 = NULL then
              PREV.next :=
                new Cell(P1.value, NULL)
              P1 := P1.next
           else
              s := min(P1.value, P2.value)
              PREV.next :=
                new Cell(s, NULL)
              if P1.value = s then
                P1 := P1.next
              if P2.value = s then
                P2 := P2.next
           PREV := PREV.next
        return OUTPUT.next