0

Determine if singly linked list is a palindrome.

Problem statement: 

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

Example:

Input:  1-> 2-> 3-> 2-> 1

Output: True

Description:

Palindrome is a word, number or sequence of characters which reads the same backward or forward. Words like noon, level or number like 12321, 161 are examples of palindrome.

We will check if given linked list is a palindrome using two approaches, one using stack and another by reversing half linked list.

        1.Using stack: 

Using stack, one way is to traverse entire linked list from head to tail and push each visited node on to stack. When entire linked list is traversed, start traversing linked list again from head and for each node check if node’s value matches to the stack pop node. If not, then return false.

Instead of pushing entire linked list on stack, lets push half linked list on stack and then as we continue to traverse linked list from middle node to tail, we will check for each node if node’s value is equal to stack pop value. If values are not equal then given linked list is not a palindrome.

For this approach time complexity is O(n) as entire linked list is traversed.Stack is used for maintaining previous nodes, so extra space required  is n/2, by ignoring constant for large linked list, space complexity will be O(n) .

        2. By reversing second half of linked list:

In this approach following steps will be followed.

  1. Traverse linked list from head to middle of linked list.
  2. Next step, is to divide linked list in two parts. One from head to middle and another from middle to tail of linked list.
  3. Reverse second linked list.
  4. Traverse and compare both linked list from head to tail.
  5. If both lists are identical, given linked list is palindrome else not.

In this approach linked list is traversed only once so time complexity will be O(n) and as constant space is required to store temporary ListNode values, space complexity will be constant, O(1).

0

Binary Tree Longest Consecutive Sequence

Problem statement:

Given a binary tree, find the length of the longest consecutive sequence path.

The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path need to be from parent to child (cannot be the reverse).

Example:

Longest Consecutive

 

Logic:

For each node we need to check if next node has a value equal to currentNode.value+1 because as per constraint only increasing order is allowed. If yes, increment count, else for that node number of elements in sequence will be 1. Before returning function call maxLength will store maximum number of elements in sequence till now. Recursively call this function for each child of node.

Code:

 

0

Max Consecutive Ones

Problem statement: (Leetcode problem no:487)

 Given a binary array, find the maximum number of consecutive 1s in this array if you can flip at most one 0.
Example:
Input:  [1,0,1,1,0]
Output: 4
Description:  Flip the first 0 will get maximum 4 consecutive 1s. If second 0 is flipped still we will get 4 consecutive 1s, as at the max one 0 flip is allowed.
Logic:
Maintain two pointers ‘low’ to keep track of start of 1s consecutive sequence and ‘zeroIndex’ pointer to mark index at which 0 is present. Whenever we encounter next 0 we will check if current length of consecutive 1s is more than previous if yes, we will update max length else max length remains same and we will update ‘low’ to mark start of next sequence of consecutive 1s.
Code:

 

0

3Sum

Problem:

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

eg.  Given array  S ={-1,0,1,2,-2,-1,-4}

Then solution set is: (-1,0,1), (-2,0,2),(-1,-1,2)

Note:

  • Elements in a triplet (a,b,c) must be in non-descending order. (i.e, abc)
  • The solution set must not contain duplicate triplets.

Logic:

To satisfy both constraints i.e. elements in triplet must be in non-descending order and no duplicate triplets, we will sort elements in array first.

We will keep first pointer at start of array, second pointer next to first pointer and third pointer at the end of array.  For each first pointer we will find a pair with it ,which in turn form a triplet whose sum is 0.

If sum is greater than 0 then we will decrease last pointer position and if sum is less than 0 then we will increment second pointer.

We need to make sure pairs are not repeated that means if numbers are repeated in array, we should skip them by increment and decrement of pointer appropriately.

Implementation:

Complexity:  O(n2)

0

Delete value from singly linked list

Problem:

Given a Linked List of Integers Delete all nodes that have value x.

Logic:

The basic thing we need to take into consideration is that given value can be present in a linked list more than once. So we will traverse to complete list while deleting a value. To keep a track if value is deleted from linked list or  if  value is not present in list, we will maintain a flag variable.

There are three spots from where you can delete the given node :

1) Node to delete is the first node :

Just assign current Head’s next as Head and delete the head ! 😀

It is possible that newly made head node also contains a same value(val that is to be deleted), eg. list [1,1,3] that is why we are checking head value repeatedly until its other that given val or head becomes null.

2) Node to delete is last node :

If given value is present in last node then we just need to make, next value of its previous node ‘null’.

3) Neither last nor first (Intermediate Node) :

Consider this linked list x->y->z and you want to delete y, then to delete y ,

x.next becomes z and y.next becomes null;

 

 

Below is implementation of this logic:

As all the nodes of linked list are traversed, time complexity of this operation is O(n).

0

Check if Singly Linked list has a cycle

Problem:

Checking if linked has a cycle . This means that there will be no ‘null’ value for address pointer in linked list.

Logic:

I.  Without extra space solution:

If  linked list has a cycle then there never going to be a null node. So it is important to decide exit condition from loop carefully.

We will assign two nodes, one to head and one to head next. If there is cycle, then there will be a point where both temporary nodes will be pointing to same node and if there is no cycle then one of them(tempNode2 because it is assigned to next to tempNode1 at start) will become null.

Time complexity for this solution is O(n)

When cycle is present in linked list then tempNode1 traverse at the max n nodes and tempNode2 will traverse through linked list faster than tempNode1 and will examine n nodes.  If cycle not present in Linked list then tempNode2 will become null after traversing n nodes. So time complexity of this solution is O(n).

II.Using extra list:

In this solution we will create a list and will add each node to the list if its not already present in that list. We will continue adding node till tempNode is not null.

This solution uses extra space so not feasible for long linked list.

Each new node will be compared with all its previous nodes. So for ‘n’ node there will be ‘n-1’ comparisons. So time complexity of this solution is O(n).

Space complexity of this solution is O(n).