// A complete working C program to demonstrate deletion in singly
// linked list
// RUN: %cml %s -o %t && %t | FileCheck %s
#include <stdio.h>
#include <stdlib.h>

// A linked list node
struct Node {
  int data;
  struct Node *next;
};

/* Given a reference (pointer to pointer) to the head of a list
and an int, inserts a new node on the front of the list. */
void push(struct Node **head_ref, int new_data) {
  struct Node *new_node = (struct Node *)malloc(sizeof(struct Node));
  new_node->data = new_data;
  new_node->next = (*head_ref);
  (*head_ref) = new_node;
}

/* Given a reference (pointer to pointer) to the head of a list
and a key, deletes the first occurrence of key in linked list */
void deleteNode(struct Node **head_ref, int key) {
  // Store head node
  struct Node *temp = *head_ref, *prev;

  // If head node itself holds the key to be deleted
  if (temp != NULL && temp->data == key) {
    *head_ref = temp->next; // Changed head
    free(temp);             // free old head
    return;
  }

  // Search for the key to be deleted, keep track of the
  // previous node as we need to change 'prev->next'
  while (temp != NULL && temp->data != key) {
    prev = temp;
    temp = temp->next;
  }

  // If key was not present in linked list
  if (temp == NULL)
    return;

  // Unlink the node from linked list
  prev->next = temp->next;

  free(temp); // Free memory
}

// This function prints contents of linked list starting from
// the given node
void printList(struct Node *node) {
  while (node != NULL) {
    printf(" %d ", node->data);
    node = node->next;
  }
}

/* Drier program to test above functions*/
int main() {
  /* Start with the empty list */
  struct Node *head = NULL;

  push(&head, 7);
  push(&head, 1);
  push(&head, 3);
  push(&head, 2);

  // CHECK: Created Linked List:
  puts("Created Linked List: ");
  // CHECK: 2 3 1 7
  printList(head);
  deleteNode(&head, 1);
  // CHECK: Linked List after Deletion of 1:
  puts("\nLinked List after Deletion of 1: ");
  // CHECK: 2 3 7
  printList(head);
  return 0;
}
