Showing posts with label Linked List. Show all posts
Showing posts with label Linked List. Show all posts

## How to print singly linked list in reverse order

If we talk about Singly Linked List then it will be a 1 way traversal from head node to tail node. But if we need to print the linked list values from tail node to head node (in reverse order) with O(N) time complexity. ???

• Its simple just we need to apply recursive algorithm where we need to start from head node and reach tail which is last node.
• Next print each node values in recursive call. By this way we can achieve printing linked list in recursive order without traversing more than once which is by time complexity O(N) only.
Lets see simple code to create Singly Linked List and printing same Linked List in reverse order with O(N) complexity.

class NODE {

int data;
NODE next;

public NODE(int data) {
this.data = data;
this.next = null;
}
}

public static void main(String[] args) {

int val[] = new int[] { 1, 5, 7, 10, 89 };

}

/*
* Recursive method to print LL in reverse order
*/
public void printLLInReverse(NODE tmp) {
if (tmp != null) {
printLLInReverse(tmp.next);
System.out.println(tmp.data);
}
}

/*
* Create linked list based on given array
*/
NODE start = null;
for (int i : val) {
NODE tmp = new NODE(i);
if (start == null) {
start = tmp;
} else {
NODE mover = start;
while (mover.next != null) {
mover = mover.next;
}
mover.next = tmp;
}
}
return start;
}
}

OUTPUT:

89
10
7
5
1

## How to delete a Node from Linked List in java

In our earlier tutorials we have seen lot of Linked List related questions and programs. On similar stage another question is how to delete a Node from a Linked List. Same way lets create a Linked List and try to delete a node from it with simple Java code.

class NODE {

int data;
NODE next = null;

public NODE(int data) {
this.data = data;
}
}

public class DeleteLLNode {

public static void main(String[] args) {

int array[] = new int[] { 11, 12, 13, 14, 15, 16, 17, 18 };
int deleteNode = 15;

DeleteLLNode obj = new DeleteLLNode();

// Create linkedlist based all array values

// Print all node values before delete

start = obj.deleteNode(start, deleteNode);

// Print all node values after delete
}

/*
* Create LinkedList and return the start pointer/node
*/

NODE start = null;
NODE tmp = null;

for (int i : array) {

tmp = new NODE(i);

if (start == null) {
start = tmp;
} else {
NODE mover = start;
while (mover.next != null) {
mover = mover.next;
}
mover.next = tmp;
}
}
return start;
}

/*
*  Print all linked list node values
*/
while(start != null) {
System.out.print(start.data +", ");
start = start.next;
}
System.out.println();
}

/*
*/
public NODE deleteNode(NODE start, int val) {
NODE tmp = start;

// If its first node to delete
if(tmp != null && tmp.data == val) {
start = start.next;
return start;
}

NODE previous = null;
while(tmp != null) {
if(tmp.data == val) {
previous.next = tmp.next;
}
previous = tmp;
tmp = tmp.next;
}
return start;
}
}

OUTPUT:

Linked List: 11, 12, 13, 14, 15, 16, 17, 18,
Linked List: 11, 12, 13, 14, 16, 17, 18,

## How to detect loop in a linked list or not

We have seen lot of posts related to LinkedList like,

Finding N'th node from the end of a Linked List
Find the middle node of a given linked list

now lets see how to detect or find whether the linked having loop or not. For example if we traverse the linked list then it will be indefinite and falls into a cyclic loop of entire linked list or within the linked list.
Lets create simple linked list by having loop and by another method lets try to find the loop present or not. We can solve/ find the loop in linked list using multiple ways like

• Storing the NODE in HashSet and checking for each put whether we have same NODE already in HashSet or not. If its present then loop present.
• Next keep 2 pointers to traverse the nodes like 1st pointer will traverse 1 NODE at a time and 2nd pointer will traverse 2 NODE's at time. At some point 1st and 2nd pointer's will be same and then loop present or else loop not present.
Lets see both implementation in a single program with 2 differnt methods.

Example's:

array[] = { 11, 12, 13, 14, 15, 16, 17, 18 }
loopValue = 14
Here LinkedList created with loop from 14 to 18

Output: Loop present

array[] = { 1,2,3,4,5,6,7,8,9}
loopValue = 1
Here LinkedList created with loop from 1 to 9

Output: Loop present

array[] = { 10,20,30,40,50,60,70,90,100 }
loopValue = 25
Here LinkedList created and we don't have any node with value 25.

Output: Loop NOT present

import java.util.HashSet;

class NODE {

int data;
NODE next = null;

public NODE(int data) {
this.data = data;
}
}

public static void main(String[] args) {

int array[] = new int[] { 11, 12, 13, 14, 15, 16, 17, 18 };
int loopValue = 14;

//int array[] = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
//int loopValue = 1;

//int array[] = new int[] { 10, 20, 30, 40, 50, 60, 70, 90, 100 };
//int loopValue = 25;

// Create linkedlist based all array values

String output1 = obj.findLoopUsingHashSet(start);
String output2 = obj.findLoopUsing2Pointers(start);

System.out.println("Using HashSet    : "+output1);
System.out.println("Using 2 pointers : "+output2);

}

/*
* Create LinkedList and return the start pointer/node
*/
public NODE createLinkedList(int[] array, int loopValue) {

NODE start = null;
NODE tmp = null;

// Pointer to hold the loop start node

for (int i : array) {

tmp = new NODE(i);

if (start == null) {
start = tmp;
} else {
NODE mover = start;
while (mover.next != null) {
mover = mover.next;
}
mover.next = tmp;
}

// pointer of the node where loop starts
if (i == loopValue) {
}
}

// Create loop from last node to linknode which has loopValue.
}

return start;
}

public String findLoopUsingHashSet(NODE start) {

HashSet<NODE> hs = new HashSet<NODE>();

while (start != null) {
if (hs.contains(start))
return "Loop present";

start = start.next;
}
return "Loop NOT present";
}

public String findLoopUsing2Pointers(NODE start) {

NODE first = start, second = start;
while(second != null && second.next != null && second.next.next != null) {
first = first.next;
second = second.next.next;
if(first == second)
return "Loop present";
}
return "Loop NOT present";
}
}

OUTPUT:

Using HashSet    : Loop present
Using 2 pointers : Loop present

## How to create simple and easy singly LinkedList in Java

Lets see simple Java code to create custom singly LinkedList and maintaining the same order. Also lets traverse the LinkedList and make sure the LinkedList created properly or not. Here we have class called NODE to store the node details like data and next link. MyLinkedList class used to create LinkedList and to print all the values in LinkedList by traversing all nodes from start to end.

class NODE {

int data;
NODE next = null;

public NODE(int data) {
this.data = data;
}
}

public static void main(String[] args) {

int array[] = new int[] { 11, 12, 13, 14, 15, 16, 17, 18 };

//Create linkedlist based all array values

//print all the values in linkedlist
}

/*
* Create LinkedList and return the start pointer/node
*/

NODE start = null;

for (int i : array) {

NODE tmp = new NODE(i);

if (start == null) {
start = tmp;
} else {
NODE mover = start;
while (mover.next != null) {
mover = mover.next;
}
mover.next = tmp;
}
}
return start;
}

/*
* Print/traverse the linkedlist all values
*/
while (start != null) {
System.out.println(start.data);
start = start.next;
}
}
}

OUTPUT:

11
12
13
14
15
16
17
18

## N'th node from the end of a Linked List

Need to find the N'th node from the end of Singly Linked List. Since its singly linked we can't traverse bidirectional and important condition is to traverse only once from start to end of the Linked List. Suppose if the length of Linked List is less than N then return -1.

Solution:
> Use 2 pointers where 1st pointer will be traversing from start to end and 2nd pointer will be starting when 1st pointer reaches N'th node.
> In such a way that when 1st pointer reaches the last node in Linked List 2nd pointer will be placed in the N'th node from last.

Let see simple Java code to implement LinkedList and to find the N'th node from last just by traversing only once.

public class FindLLNode {

int data;

this.data = data;
this.next = null;
}
}

public static void main(String[] args) {

int val[] = new int[] { 23, 7, 10, 45, 9, 11 };

int findNode = 3;

FindLLNode obj = new FindLLNode();

int nthNodeVal = obj.findLLNode(start, findNode);

System.out.println("nth Node Value from last : " + nthNodeVal);
}

LinkedList start = null, temp = null;
for (int i : val) {

if (start == null) {
start = temp = node;
} else {
temp.next = node;
temp = temp.next;
}
}
return start;
}

private int findLLNode(LinkedList start, int findNode) {

LinkedList p1 = start, p2 = start;
int i = 0;
boolean flag = false;
while (p1 != null) {
if (i >= findNode) {
p2 = p2.next;
flag = true;
}
p1 = p1.next;
i++;
}
if (!flag)
return -1;
return p2.data;
}
}

OUTPUT:

3rd Node Value from last : 45

## Find the middle node of a given linked list

Given a singly linked list, find the middle NODE of the linked list. For example, if given linked list is 1->2->3->4->5 then output should be 3.
If there are even nodes, then there would be two middle nodes, we need to print second middle element. For example, if given linked list is 1->2->3->4->5->6 then output should be 4.
CONDITION:
• Need to traverse the linked list only once.

public class MiddleNode {

class NODE {

int data;
NODE next;

public NODE(int data) {
this.data = data;
this.next = null;
}
}

public static void main(String[] args) {

MiddleNode obj = new MiddleNode();

int val[] = new int[] { 3, 6, 7, 8, 9, 11, 13, 15, 17, 22, 24, 25, 28};

/* Get middle NODE */
NODE middleNode = obj.getMiddleNode(start);

System.out.println("MIDDLE NODE : "+middleNode.data);
}

/*
* Create linked base based on given array
*/
NODE start = null;
for (int i : val) {
NODE tmp = new NODE(i);
if (start == null) {
start = tmp;
} else {
NODE mover = start;
while (mover.next != null) {
mover = mover.next;
}
mover.next = tmp;
}
}
return start;
}

/*
* Getting middle NODE just by traversing only once
*/
public NODE getMiddleNode(NODE start) {
NODE slow = start, fast = start;
while(fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
if(fast.next != null) {
slow = slow.next;
}
return slow;
}
}

OUTPUT:

MIDDLE NODE : 13

## Merge 2 Sorted Linked Lists

Function that takes two lists, each of which is sorted in increasing order, and merges the two together into one list which is in increasing order. The new list should be made by splicing
together the nodes of the first two lists.
For example if the first linked list a is 5->10->15 and the other linked list b is 2->3->20, then SortedMerge() should return a pointer to the head node of the merged list 2->3->5->10->15->20.

There are many cases to deal with: either ‘a’ or ‘b’ may be empty, during processing either ‘a’ or ‘b’ may run out first, and finally there’s the problem of starting the result list empty, and building it up while going through ‘a’ and ‘b’.

{ 3, 6, 7, 8, 9 }
{ 1, 5, 7, 10, 89 }
OUTPUT: 1, 3, 5, 6, 7, 7, 8, 9, 10, 89

{}
{3, 4, 7, 8}
OUTPUT: 3, 4, 7, 8
Lets see simple Java code to get merge 2 sorted linked list without creating new (3rd) linked list and only by splicing both list nodes.

class NODE {

int data;
NODE next;

public NODE(int data) {
this.data = data;
this.next = null;
}
}

public static void main(String[] args) {

int val1[] = new int[] { 3, 6, 7, 8, 9 };
int val2[] = new int[] { 1, 5, 7, 10, 89 };

/* Create 1st linked list */

/* Create 2nd linked list */

NODE print = start;
while (print != null) {
System.out.println("----> " + print.data);
print = print.next;
}
}

/*
* Create linked list based on given array
*/
NODE start = null;
for (int i : val) {
NODE tmp = new NODE(i);
if (start == null) {
start = tmp;
} else {
NODE mover = start;
while (mover.next != null) {
mover = mover.next;
}
mover.next = tmp;
}
}
return start;
}

/*
*/
public NODE mergeLinkedList(NODE first, NODE second) {

if (first == null)
return second;
if (second == null)
return first;

NODE start = null;
NODE mover = null;

while (first != null && second != null) {
if (start == null) {
if (first.data <= second.data) {
start = mover = first;
first = first.next;
} else if (second.data <= first.data) {
start = mover = second;
second = second.next;
}
} else {
if (first.data <= second.data) {
mover.next = first;
first = first.next;
} else if (second.data <= first.data) {
mover.next = second;
second = second.next;
}
mover = mover.next;
}
}
if (first == null) {
while (second != null) {
mover.next = second;
second = second.next;
mover = mover.next;
}
}
if (second == null) {
while (first != null) {
mover.next = first;
first = first.next;
mover = mover.next;
}
}
return start;
}
}
OUTPUT:

----> 1
----> 3
----> 5
----> 6
----> 7
----> 7
----> 8
----> 9
----> 10
----> 89