Remove Linked List Elements - LeetCode

Remove all elements from a linked list of integers that have value val.

Example:

Input:  1->2->6->3->4->5->6, val = 6
Output: 1->2->3->4->5

Java Solution :

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode helper = new ListNode(0);
        ListNode p = helper;
        helper.next = head;
        
        while(p.next !=null){
            if(p.next.val == val){
                p.next = p.next.next;
            }else{
                p = p.next;
            }
        }
        return helper.next;
    }
}

Template for Two Pointer in Linked List

 Steps :

1. First we need to initialize the slow pointer and fast pointer.

    // Initialize slow and fast pointers.
     ListNode slow = head;
     ListNode fast  = head;
   // Change the condition according to the problem.
  // Remember to avoid error prone.
    while(slow != null && fast !=null && fast.next!=null){
    slow = slow.next; // move slow pointer one step each time
    fast = fast.next.next; // move fast pointer two steps each time
    if(slow == fast){
    return true;
    }
    }
    return false;


Note :

1. Always make sure while  calling the next on the current node.
 
    Getting the next node of the null node will cause errors.

    So before we examine fast and fast.next make sure they are not null.

2. Carefully define the end conditions of the loop.

    Run several examples to make sure your end conditions will not result in error.


Complexity Analysis :

It is easy to analyze the space complexity. If you only use pointers the space complexity is O(1).

But the time complexity will change according to the problem.

In above scenario slow pointer moves one step each time and fast pointer moves two steps each time.

1. If there is no Cycle the fast pointer will move the end of the list in N/2 steps.

2. If there is a Cycle the fast pointer takes M times to catch the slow pointer where M is the length of the Cycle in the List.

Obviously M<=N , So we run the loop N times and it needs constant time . So the time complexity is O(N) in total.

Always try to calculate the worst case scenarios by taking different examples .

Two Pointer in Linked List

Let's think of this case :

Suppose we have a Linked List and we need to check whether it has  Cycle or not.

Consider two pointers one is slow pointer and the other one is fast pointer.

So the slow pointer moves one step and the fast pointer moves in two steps .


Imagine two runners running on a circular track :

The fast runner eventually meets the slow runner some where on the track.

Exactly in the same manner :

1. If the fast pointer meets slow pointer it has Cycle.

2. If the fast pointer reaches the end of the linked list means it has no Cycle.


It is always safe that slow pointer moves one step at a time and fast pointer moves two steps at a time.

For each iteration the fast pointer will move one step ahead of the slow pointer and will meet slow pointer after m iterations.

Design Singly Linked List

Think we have to design Singly Linked List :

What should come into our mind ???????????

 Linked List will have value field and reference to next node field.

Structure Definition of a node in a Singly Linked List :

// Definition for singly Linked List 

public class SinglyListNode {

    int val;

    SinglyListNode next;

    SinglyListNode(int x){

         val = x;

      }

}

Initiate a new Linked List : Represent a linked list using the head node.

class MyLinkedList {

       private SinglyListNode head;

       public MyLinkedList(){

       head = null;

       }

}

Traverse the linked list to get element by index.

private SinglyListNode getNode(int index){

 SinglyListNode cur = head;

 for(int i =0 ; i < index && cur != null ; ++i){

 cur = cur.next;

 }

return cur;

}

//Function to return last element of the List.

private SinglyListNode getTail(){

SinglyListNode cur = head;

while(cur !=null && cur.next !=null){

cur = cur.next;

}

return cur;

}

// Function to return value of index-th node in the linked list.

private int get(int index){

SinglyListNode cur = head;

for(int i =0 ;i < index && cur != null ; ++i){

cur = cur.next;

}

return cur == null ? -1 : cur.val;

}

// Function to add a new Node.

// Here adding the node before the first element.

public void addAtHead (int val){

SinglyListNode cur = new SinglyListNode(val);

cur.next = head;

head = cur;

return;

}

// Here adding a node to the last element of the linked list.

public void addAtTail(int val){
SinglyListNode cur = new SinglyListNode(val);
if(head == null){
cur.next = head;
head = cur;
return;
}

SinglyLinkedNode dummy = head;
while(dummy.next !=null){
dummy = dummy.next;
}
dummy.next = cur;
}


// Add at particular index and the val.

public void addAtIndex(int val , int index){

SinglyListNode cur = new SinglyListNode(val);
if(index == 0){
cur.next = head;
head = cur;
return;
}

SinglyListNode prev = getNode(index-1);
if(prev == null){
return;
}

SinglyListNode next = prev.next;
cur.next = next;
prev.next = cur;

}


Delete a Node :

public void deleteIntIndex(int index){

SinglyListNode cur = getNode(index);
if(cur == null){
return;
}

SinglyListNode prev = getNode(index-1);
SinglyListNode next = cur.next;

if(prev != null){
prev.next = next;
} else {
head = next;
}
}

Singly Linked List - Introduction

Each node in a Singly Linked List contains a value and a  reference to link to the next node.

Linked list organizes all the nodes in a sequence.

Example of an Singly Linked List :

Here the nodes are linked together.


// Definition for Singly Linked List

public class SinglyListNode {
int val;
SinglyListNode next;
SinglyListNode (int x){
val = x;
}
}

In most cases we use the head node to represent the whole list.

Operations :

In LinkedList we can't retrieve the element in constant time like arrays .

If we want to fetch ith element we have to traverse from the head node one by one .

It takes O(N) on average to visit an element where N is the length of the linked list.

For Example in above singly Linked List if we want to retrieve the element '1' we need to traverse one by one till it reaches element '1' from head node 5 using "next" .

So we may rise a Question what is the use of List when we can access elements in O(1) time using arrays ? (In Retrieval Lists are bad in performance compared to Arrays).

Linked List are useful and benefitted in insertion and deletion .


Add Operation :
https://techyield.blogspot.com/2019/06/singly-linked-list-add-operation.html


Delete Operation :
https://techyield.blogspot.com/2019/06/singly-linked-list-delete-operation.html

Singly Linked List - Delete Operation

Example :


         3 --------> 4 -------------> 5 ------------> 6


                      prev                 cur                   next


Suppose we want to delete element '5' here . 

1. We need to traverse the linked list first until we reach prev node .

2.  So once we reach prev node then we need to point prev reference to next .


         Prev.next = cur.next;
       

           After that :


     3 -----------> 4 -------------> 6

That's how we delete an element.

Anyway it takes O(n) to traverse entire list and space complexity O(1).


Delete the First Node

1. In general entire LinkedList is represented with head node.

2. Just point head to head.next

   This is how you will delete the head node.

Singly Linked List - Add Operation

Inserting an element in Middle of the Linked List :

Consider :

            3 ---> 4 ---> 5 ---> 7

                     prev    next

 Suppose we want to insert an element with value 8 after 4 .

     1. Initialize a new node cur with given value 8.

                    cur.value =  8;

     2.  Link the cur next node to prev next node next.

                   cur.next = prev.next;

     3.  Link the prev next node to current node.

                   prev.next = current;

So here we no need to move all the elements like arrays.  So we can insert the element in List in O(1) time complexity. Which is very efficient.

Inserting an element at the Beginning :

    In list we use the head node to represent the entire list. 

    So we should update the head when representing the entire list.

   1. First create a new node current with the value.

   2. Second point current node next to head node.

  3.  Update the head node by pointing to current node.