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

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).

0

Print singly linked list in reverse order

Problem:

Printing singly linked list is a little tricky problem because singly linked list only stores address to of the next node, no previous node address is stored in any node.

Logic:

This problem can be solved easily using recursion. Recursively call PrintReverse function till root is not null and start print.

For last node his next is null, so for that null function will return and executing line below recursive call will start execution which will start printing node values. As print line execution starts from last node, linked list will be printed in reverse order.

Implementation:

0

Reverse singly linked list

Problem:

In singly linked list, each node contains reference to next node. Address of previous node is not stored in any node, so reverse a singly linked list is a tricky question.

Logic:

For start we will assign previous node as null and currentNode as head of linked list.Till we reach to the last node of list, first store next node in a temporary node and make current node’s next as previous node. Then for next iteration, current node become previous node and nextNode becomes CurrentNode.

Implementation: