content: package linkedlist;
  
  public class DeleteNodeWithKey {
  
  
      /*
       * Given head of a linked list and a key, delete node with this given key from the linked list.
       *
       * */
  
      /*
       * Step 1: find the key in the linked list. Have two pointers: current and previous as we iterate the linked list.
       * Step 2: If the key is found in the linked list, then current pointer would be pointing to the node
       *         containing key to be deleted and previous should be pointing to the node before the key node.
       * Step 3: Update current and previous pointers, as we iterate through the linked list.
       *
       * Runtime Complexity:
       *  Linear, O(n)
       *
       *  Memory Complexity:
       *   Constant, O(1)
       * */
  
  
      public static class LinkedList {
  
          private Node head;
          public Node deleteNode(Node head, int key) {
              Node current = head;
              Node previous = null;
              while (current != null) {
                  if(current.data == key) {
  
                      if(current == head) {
                          head = head.next;
                          current = head;
  
                      } else {
                          previous.next = current.next;
                          current = current.next;
                      }
  
                  } else {
                      previous = current;
                      current = current.next;
                  }
              }
  
              return head;
          }
  
          public void printNode(Node node) {
              while (node != null) {
                  System.out.print(node.data + " ");
                  node = node.next;
              }
          }
  
          public static class Node {
              private int data;
              private Node next;
              public Node(int data) {
                  this.data = data;
                  this.next = null;
              }
          }
      }
  
  
      public static void main(String [] args) {
          LinkedList linkedList = new LinkedList();
          linkedList.head = new LinkedList.Node(1);
          linkedList.head.next =  new LinkedList.Node(2);
          linkedList.head.next.next =  new LinkedList.Node(3);
          linkedList.head.next.next.next = new LinkedList.Node(4);
  
          linkedList.printNode(linkedList.head);
          linkedList.head = linkedList.deleteNode(linkedList.head, 2);
          System.out.println("");
          linkedList.printNode(linkedList.head);
  
      }
  }
  