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.

Word Search - LeetCode

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

Java Solution :

class Solution {
    public boolean exist(char[][] board, String word) {
        if(board == null || word == null)
            return true;
        for(int i =0 ; i < board.length; i++){
            for(int j=0; j < board[i].length ; j++){
                if(board[i][j] == word.charAt(0) && dfs(i,j,0,word,board))
                    return true;
            }
        }
        return false;
    }
    
    public boolean dfs(int i ,int j , int count , String word, char[][] board){
        
        if(count == word.length())
            return true;
        
        if(i<0 || j<0 || i >= board.length || j >= board[i].length || board[i][j] != word.charAt(count))
              return false;
        
        char temp = board[i][j];
        board[i][j] = ' ';
        boolean found = dfs(i+1,j,count+1,word,board) || dfs(i-1,j,count+1,word,board) || dfs(i,j+1,count+1,word,board) ||           dfs(i,j-1,count+1,word,board);
        board[i][j] = temp;
        
        return found;
    }
}

Word Search - LeetCode

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

Java Solution :

class Solution {
    public boolean exist(char[][] board, String word) {
        if(board == null || word == null)
            return true;
        for(int i =0 ; i < board.length; i++){
            for(int j=0; j < board[i].length ; j++){
                if(board[i][j] == word.charAt(0) && dfs(board,i,j,0,word))
                    return true;
            }
        }
        return false;
    }
    
    public boolean dfs(char[][] board,int i , int j, int count,String word){
        if(count == word.length())
            return true;
        
        if(i<0 || i >=board.length || j<0 || j>= board[i].length || board[i][j] != word.charAt(count) ){
            return false;
        }
        
        char temp = board[i][j];
        board[i][j] = ' ';
        boolean found = dfs(board,i+1,j,count+1,word) || dfs(board,i-1,j,count+1,word) || dfs(board,i,j+1,count+1,word) || dfs(board,i,j-1,count+1,word);
        board[i][j]= temp;
        
        return found;
    }
}

Convert Sorted Array to Binary Search Tree - LeetCode

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

Java Solution :

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if(nums == null || nums.length==0)
            return null;
       
        return constructarraytobst(nums,0,nums.length-1);  
    }
    
    public TreeNode constructarraytobst(int[] nums , int left , int right){
        if(left > right)
          return null;
        
        int mid = left + (right-left)/2;
        TreeNode current = new TreeNode(nums[mid]);
        current.left = constructarraytobst(nums,left,mid-1);
        current.right = constructarraytobst(nums,mid+1,right);
        return current;
    }
}

Linked List Cycle - LeetCode

Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Follow up:

Can you solve it using O(1) (i.e. constant) memory?

Java Solution 1:

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null)
            return false;
        ListNode slow = head;
        ListNode fast = head.next;
        while(slow != fast){
            if(fast == null || fast.next == null )
                return false;
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }
}

Java Solution 2:

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> nodeSeen = new HashSet<>();
        while (head != null){
            if(nodeSeen.contains(head))
                return true;
            else
                nodeSeen.add(head);
            head = head.next;
        }
        return false;
    }
}

Palindrome Linked List - LeetCode

Given a singly linked list, determine if it is a palindrome.

Example 1:

Input: 1->2
Output: false

Example 2:

Input: 1->2->2->1
Output: true

Follow up:
Could you do it in O(n) time and O(1) space?

Java Solution :

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null)
            return true;
        ListNode prev = new ListNode(head.val);
        ListNode dummy = head;
        while(dummy.next != null){
            ListNode temp = new ListNode(dummy.next.val);
            temp.next = prev;
            prev = temp;
            dummy = dummy.next;
        }
        
        ListNode last = prev;
        ListNode first = head;
        while(first!=null && last!=null){
            if(first.val == last.val){
                first = first.next;
                last = last.next;
            }else{
                return false;
            }
            
        }
        return true;
            
    }
}