linked_lists.ts

type LinkedList<T> = {
    value: T,
    next: LinkedList<T> | null
}

const cons = (value: number, next: LinkedList<number> | null = null) => {
    return { value, next }
}

const lookup = (
    list: LinkedList<number> | null,
    index: number): LinkedList<number> | null => {

    if (!list) {
        return null
    }

    if (index === 0) {
        return list
    }

    if (!list.next) {
        return null
    }

    return lookup(list.next, index - 1)
}

const last = (list: LinkedList<number>): LinkedList<number> =>
    list.next ? last(list.next) : list


const lastIndex = <T,>(arr: T[]) => arr.length - 1

const arrayLast = <T,>(arr: T[], index = lastIndex(arr)) => arr[index]

const arrayBody = <T,>(arr: T[], index = lastIndex(arr)) => arr.slice(0, index)


const fromArray = (arr: number[], list: LinkedList<number> | null = null):
    LinkedList<number> | null => {
    if (arr.length === 0) {
        return list
    }

    const body = arrayBody(arr)
    const lastElement = arrayLast(arr)

    return fromArray(body, cons(lastElement, list))
}

const fromLinked = (list: LinkedList<number> | null, arr: number[] = []): number[] => {
    if (list === null) {
        return arr
    }

    const { next, value } = list;
    return fromLinked(next, [...arr, value])

}

const removeByIndex = (
    original: LinkedList<number> | null,
    index: number, list = original
): LinkedList<number> | null => {
    if (!list || !list.next) {
        return null
    }

    if (index === 1 && list.next) {
        list.next = list.next.next;
        return original
    }

    return removeByIndex(original, index - 1, list.next)
}


const deleteDuplicates = (original:LinkedList<number> | null, list = original):
    LinkedList<number>| null => {

    if (list === null) {
        return original
    }

    if (list.next) {
        if (list.value === list.next.value) {
            list.next = list.next.next
            return deleteDuplicates(original, list)
        }
    }


    return deleteDuplicates(original, list.next)
}


const findDiff = (list: LinkedList<number> | null, val: number):
    LinkedList<number> | null => {
    if (list === null) {
        return null
    }
    const { value } = list;
    if (value !== val) {
        return list
    }

    return findDiff(list.next, val)

}
const removeAllDuplicates = (
    original: LinkedList<number> | null,
    sentinel: LinkedList<number> = cons(0, original),
    list: LinkedList<number> | null = sentinel
): LinkedList<number> | null => {
    if (original === null) {
        return null
    }

    if (!list) {
        return sentinel.next
    }

    if (list && list.next && list.next.next && list.next.value === list.next.next.value) {
        list.next = findDiff(list.next, list.next.value)

        return removeAllDuplicates(original, sentinel, list)
    } else {
        return removeAllDuplicates(original, sentinel, list.next)

    }
}

console.clear()
const linkedList = fromArray([1, 1, 2, 2, 3, 3, 4, 4, 5])

console.log('RESULT:', fromLinked(deleteDuplicates(linkedList)))

const swapPairs = (
    original: LinkedList<number> | null,
    sentinel: LinkedList<number> = cons(0, original),
    list: LinkedList<number> | null = sentinel
): LinkedList<number> | null => {
    if (original === null) {
        return null
    }

    if (!list) {
        return sentinel.next
    }

    if (list && list.next && list.next.next) {
        const smallNext = list.next;

        const bigNext = list.next.next;

        smallNext.next = bigNext.next

        list.next = bigNext
        bigNext.next = smallNext

        list.next = bigNext

        return swapPairs(original, sentinel, list.next.next)
    } else {
        return swapPairs(original, sentinel, list.next)
    }
}



const swap = (
  original: LinkedList<number> | null,
  k: number,
  list: LinkedList<number> | null = original,
  array: LinkedList<number>[] = []
): LinkedList<number> | null => {
  if (original === null) {
    return null
  }
  if (original.next === null) {
    return original
  }
  const index = k - 1

  if (list === null) {
    let smallNext = array[index]
    let bigNext = array[array.length - k]

    if (smallNext && bigNext) {

      let smallValue = smallNext.value
      let bigValue = bigNext.value

      smallNext.value = bigValue
      bigNext.value = smallValue

      return original

    }
  } else {

    array.push(list)



    return swap(original, k, list.next, array)
  }
}

function addTwoNumbers(
  l1: LinkedList<number> | null,
  l2: LinkedList<number> | null,
  carry = 0,
  current: LinkedList<number> = cons(0),
  result = current
) {
  if (l1 === null && l2 === null) {
    if (carry === 1) {
      current.next = cons(carry)
      return result.next
    }
    return result.next
  }

  if (l1 && l2) {
    let val1 = l1.value;
    let val2 = l2.value;
    let initial = val1 + val2 + carry;
    let isMoreThan10 = initial >= 10
    let sum = isMoreThan10 ? initial % 10 : initial;
    let newCarry = isMoreThan10 ? 1 : 0;
    current.next = cons(sum)


    return addTwoNumbers(l1.next, l2.next, newCarry, current.next, result)
  }
  if (l1 === null && l2) {
    let initial = l2.value + carry;

    let isMoreThan10 = initial >= 10
    let sum = isMoreThan10 ? initial % 10 : initial;
    let newCarry = isMoreThan10 ? 1 : 0;
    current.next = cons(sum)
    return addTwoNumbers(null, l2.next, newCarry, current.next, result)

  }

  if (l1 && l2 === null) {
    let initial = l1.value + carry;
    console.log({ initial })

    let isMoreThan10 = initial >= 10
    let sum = isMoreThan10 ? initial % 10 : initial;
    let newCarry = isMoreThan10 ? 1 : 0;
    current.next = cons(sum)
    return addTwoNumbers(l1.next, null, newCarry, current.next, result)

  }


};

const list1 = fromArray([9, 9, 9, 9, 9, 9, 9])
const list2 = fromArray([9, 9, 9, 9])

console.log('RESULT:', fromLinked(addTwoNumbers(list1, list2)))
// [8,9,9,9,0,0,0,1]