#include <stdio.h>
#include <stdlib.h>

// how many bytes is this struct?
// 12 bytes (on my machine)
struct node {
  int data;
  struct node *next;
  struct node *prev;
};

struct node *create_node(int data, struct node *next);
struct node *insert_at_tail(int data, struct node *head);
void print_ll(struct node *head);
int size_of_ll(struct node *head);
struct node *remove_at_index(struct node *head, int index);
struct node *remove_at_tail(struct node *head);
struct node *sum_lls(struct node *linked_list_1, struct node *linked_list_2);

struct node *remove_at_index(struct node *head, int index) {
  struct node *current = head;
  struct node *prev = NULL;
  int counter = 0;

  // empty case
  if (current == NULL) {
    return NULL;
  }

  while (current->next != NULL && counter != index) {
    prev = current;
    current = current->next;
    counter++;
  }
  // this is the case where we are at end of list, but counter is less than
  // index
  if (counter != index) {
    return head;
  }

  if (prev == NULL) {
    free(current);
    return NULL;
  }

  // to get here, counter IS index (at the right position), and we are not
  // beyond end of LL here, we want to delete current and hook prev to point to
  // current's next. and free current.
  prev->next = current->next;
  free(current);

  return head;
}

// insert at the position passed in.
// so 1 -> 2 -> 3, and index 1 data 1
// 1 -> 1-> 2 -> 3
struct node *insert_at_index(int data, struct node *head, int index) {
  index--;
  struct node *current = head;
  int counter = 0;

  // empty case
  if (current == NULL) {
    return NULL;
  }

  while (current->next != NULL && counter != index) {
    current = current->next;
    counter++;
  }

  if (counter != index) {
    return head;
  }

  // we want to add a new node after current.
  struct node *new_node = create_node(data, current->next);
  current->next = new_node;
  return head;
}

// Remove's the last node of a linked list
// Traverse every element until you find the NULL pointer in next, then remove
struct node *remove_at_tail(struct node *head) {
  struct node *current = head;
  struct node *prev = NULL;

  // empty case
  if (current == NULL) {
    return NULL;
  }

  while (current->next != NULL) {
    prev = current;
    current = current->next;
  }

  // for the case that prev was NULL
  if (prev == NULL) {
    free(current);
    return NULL;
  }

  // if there was something in prev, then hook it all back up...
  prev->next = NULL;
  free(current);

  return head;
}

// a function which takes a linked list, and adds a new node at the end.
// is append a node (at the end of the LL)
struct node *insert_at_tail(int data, struct node *head) {
  struct node *current = head;

  // empty case
  if (current == NULL) {
    return create_node(data, NULL);
  }

  // if head is NULL, we are trying to dereference it to check ->next.
  // reassign current to current->next UNTIL current-> next is NULL.
  while (current->next != NULL) {
    current = current->next;
  }

  current->next = create_node(data, NULL);
  return head;
}

struct node *create_node(int data, struct node *next) {
  // create the node on the heap
  struct node *new_node = malloc(sizeof(struct node));

  // assign data and next
  new_node->data = data;
  new_node->next = next;

  return new_node;
}

// will it work if it's empty?
// will it work if first node, a node within a LL, and the tail node
void print_ll(struct node *head) {
  struct node *current = head;
  while (current != NULL) {
    printf("%d -> ", current->data);
    current = current->next;
  }
  printf("NULL \n");
}

int size_of_ll(struct node *head) {
  struct node *current = head;
  int counter = 0;
  while (current != NULL) {
    current = current->next;
    counter++;
  }
  return counter;
}

struct node *sum_lls_jagged(struct node *linked_list_1,
                            struct node *linked_list_2) {
  struct node *curr_1 = linked_list_1;
  struct node *curr_2 = linked_list_2;
  struct node *new_ll = NULL;

  // checks that we have not reached the end of the lists
  while (curr_1 != NULL && curr_2 != NULL) {
    int sum = curr_1->data + curr_2->data;
    new_ll = insert_at_tail(sum, new_ll);

    // iterates both linked lists
    curr_1 = curr_1->next;
    curr_2 = curr_2->next;
  }

  // curr_1 has more nodes
  while (curr_1 != NULL) {
    new_ll = insert_at_tail(curr_1->data, new_ll);
    curr_1 = curr_1->next;
  }

  while (curr_2 != NULL) {
    new_ll = insert_at_tail(curr_2->data, new_ll);
    curr_2 = curr_2->next;
  }

  return new_ll;
}

// iterate through each node in both lists
// add a new node to the new list, containing the sum
// return the new list head pointer
struct node *sum_lls(struct node *linked_list_1, struct node *linked_list_2) {
  struct node *curr_1 = linked_list_1;
  struct node *curr_2 = linked_list_2;
  struct node *new_ll = NULL;

  // checks that we have not reached the end of the lists
  while (curr_1 != NULL && curr_2 != NULL) {
    int sum = curr_1->data + curr_2->data;
    new_ll = insert_at_tail(sum, new_ll);

    // iterates both linked lists
    curr_1 = curr_1->next;
    curr_2 = curr_2->next;
  }

  return new_ll;
}

int main(void) {
  // creating the first node
  // next can't be uninitialised
  struct node *head_1 = insert_at_tail(1, NULL);
  struct node *head_2 = insert_at_tail(1, NULL);
  head_1 = insert_at_tail(6, head_1);
  head_1 = insert_at_tail(8, head_1);
  head_1 = insert_at_tail(1, head_1);
  head_1 = insert_at_tail(1, head_1);
  head_1 = insert_at_tail(1, head_1);

  head_2 = insert_at_tail(2, head_2);
  head_2 = insert_at_tail(8, head_2);
  head_2 = insert_at_tail(0, head_2);
  head_2 = insert_at_tail(1, head_2);
  head_2 = insert_at_tail(1, head_2);
  head_2 = insert_at_tail(1, head_2);
  head_2 = insert_at_tail(1, head_2);

  printf("Linked list 1:\n");
  print_ll(head_1);

  printf("Linked list 2:\n");
  print_ll(head_2);

  printf("Linked summed list:\n");
  print_ll(sum_lls_jagged(head_1, head_2));

  printf("Linked null summed list: ");
  print_ll(sum_lls_jagged(NULL, NULL));

  return 0;
}