linklist
1.Inset a node in link list nd print
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package linklist;
class Node
{
int data;
Node next;
Node(int d)
{
next=null;
data=d;
}
}
*/
public class problem5_to_nth_node {
Node head;
class Node
{
int data;
Node next;
Node(int d)
{
next=null;
data=d;
}
}
void add(int d)
{
/* Node n1;
if(head==null)
{
head.data=data;
head.next=null;
}
else
{
n1=head;
while(n1.next!=null)
{
n1=n1.next;
}
n1.next=null;
}
Error
*/
Node n1=new Node(d);
if(head==null)
{
head=n1;
// head.data=d;
}
else
{
Node n2;
n2=head;
while(n2.next!=null)
{
n2=n2.next;
}
n2.next=n1;
//n2.next.data=d;
n2.next.next=null;
}
}
public void printdata()
{
Node n2;
n2=head;
while(n2!=null)
{
System.out.println(n2.data);
n2=n2.next;
}
}
public static void main(String[] args)
{
// LinkedList l1=new LinkedList();
problem5_to_nth_node l1=new problem5_to_nth_node();
l1.add(1);
l1.add(2);
l1.add(3);
l1.add(4);
l1.add(5);
l1.add(6);
// Node n1=new Node(1);
l1.printdata();
}
}
Note:
import java.util.Scanner;
public class problem5_to_nth_node {
Node head;
class Node
{
int data;
Node next;
Node(int d)
{
next=null;
data=d;
}
}
void add(int d)
{
Node n1=new Node(d);
if(head==null)
{
head=n1;
// head.data=d;
}
else
{
Node n2;
n2=head;
while(n2.next!=null)
{
n2=n2.next;
}
n2.next=n1;
//n2.next.data=d;
n2.next.next=null;
}
}
public void printdata()
{
Node n2;
n2=head;
while(n2!=null)
{
System.out.println(n2.data);
n2=n2.next;
}
}
2.find nth node from last in 1 scan //remove nth node from last //one scan
public Node print(Node head, int n) //delete nth node from last
{
if(head==null)
{
return null;
}
ListNode slow=head;
ListNode fast=head;
for(int i=0;i<n;i++)
{
fast=fast.next;
}
if(fast==null)
{
head=head.next;
return head;
}
while(fast.next!=null)
{
slow=slow.next;
fast=fast.next;
}
slow.next=slow.next.next;
return head;
}
BUILD SUCCESSFUL (total time: 3 seconds)
///find n-l+1 node for nth node from last
3..To detect cycle in the link list and find starting point
public ListNode detectCycle(ListNode head)
{
ListNode slow=head;
ListNode fast=head;
while(slow!=null && fast!=null && fast.next!=null)
{
slow=slow.next;
fast=fast.next.next;
if(slow==fast)
{
fast=head;
while(slow!=fast)
{
slow=slow.next;
fast=fast.next;
}
return slow;
}
}
return null;
}
}
3.remove duplicate from unsorted linklist.
package withconstructor;
import java.util.HashSet;
public class removedups_2_1 {
Node head;
class Node
{
Node next;
int data;
Node(int d)
{
next=null;
data=d;
}
}
public void add(int d1)
{
Node n1=new Node(d1);
if(head==null)
{
head=n1;
head.data=d1;
head.next=null;
}
else
{
Node n2;
n2=head;
while(n2.next!=null)
{
n2=n2.next;
}
n2.next=n1;
n1.data=d1;
n1.next=null;
}
}
public void print()
{
Node n2;
n2=head;
n2.data=head.data;
while(n2!=null)
{
System.out.print(n2.data);
n2=n2.next;
}
}
public void removedup()
{
HashSet s=new HashSet();
Node n1=head;
// n1.data=head.data;
Node previous=null;
while(n1!=null)
{
if(s.contains(n1.data))
{
previous.next=n1.next;
}
else
{
s.add(n1.data);//we cant write here "s.add(n1);"
//bcz we can insert data in hashset not node
previous=n1;
}
n1=n1.next;
}
}
public static void main(String[] args)
{
removedups_2_1 t1=new removedups_2_1();
t1.add(2);
t1.add(3);
t1.add(4);
t1.add(2);
t1.add(6);
t1.add(7);
t1.removedup();
t1.print();
}
}
4.delete the middle node from link list.
/*package whatever //do not write package name here */
import java.io.*;
class GFG {
Node head;
class Node
{
Node next;
int data;
Node(int d1)
{
next=null;
data=d1;
}
}
public void add(int d)
{
Node n1=new Node(d);
if(head==null)
{
head=n1;
head.next=null;
}
else
{
Node n2;
n2=head;
while(n2.next!=null)
{
n2=n2.next;
}
n2.next=n1;
n2.next.next=null;
}
}
public void deletemiddle()
{
Node n3;
n3=head;
Node n4;
n4=head;
Node previous=null;
while(n3!=null && n3.next!=null)
{
n3=n3.next.next;//1->2->3->4->5->6
//1->3->5->null
if(n3!=null)
{
previous=n4;
n4=n4.next; //1->2->3->4->5->6
}
}
previous.next=n4.next;
}
/*
public void delete_middle()
{
if(head==null || head.next==null || head.next.next==null)
{
return;
}
else
{
Node slow=head;
Node fast=head;
Node prev=null;
while(slow!=null && fast!=null && fast.next!=null && fast.next.next!=null)
{
prev=slow;
slow=slow.next;
fast=fast.next.next;
}
prev.next=slow.next;
}
//1 2 3 4 2 5
//1 2 4 2 5
//1 2 4 2 5
}*/
public void print()
{
while(head!=null)
{
System.out.print(head.data);
head=head.next;
}
}
public static void main (String[] args) {
GFG g1=new GFG();
g1.add(1);
g1.add(2);
g1.add(3);
g1.add(4);
g1.add(5);
g1.add(6);
g1.add(7);
g1.deletemiddle();
g1.print();
}
}
Output:
123567
Note:
To delete a node: public void deleteNode(ListNode node)
{
node.val=node.next.val;
node.next=node.next.next;
}
5. Insert node in sorted link list
public void sorted(int d1)
{
Node n2=new Node(d1);
Node n4;
n4=head;
Node previous=null;
if(n4!=null)
{
while(n4.data<d1)
{
previous=n4; // store that node after that we have to insert
n4=n4.next;
}
previous.next=n2; //prev dot next equals to new node
n2.next=n4; //now link new node to next
}
}
6.reverse the singly link list
public void rev()
{
Node prev=null;
Node current=head;
while(current!=null)
{
Node temp=current.next;
current.next=prev;
prev=current;
current=temp;
}
head=prev;
}
7.find the middle node in linklist
-->efficeient approach..take time o(n) and space o(1) and run for single scan
public void middle()
{
Node n1,n2; //its to move node using slow and fast algirithm
n1=n2=head;
int i=0;
while(n1.next!=null)
{
if(i==0)
{
n1=n1.next; //moving this node one time
i=1;
}
else if(i==1) //it should be else if then we can think better….but not need
{
n1=n1.next; //moving n1 agail
n2=n2.next;
i=0;
}
}
System.out.println(n2.data); //to print middle node
}
8. Print node from last.
-->for this we have to use recursion to print in single scan. time:o(n) space o(n)
public void reversePrint(Node head)
{
Node n1=head;
if(head==null)
{
return;
}
else
{
reversePrint(n1.next); //recursion it will store like stack and print in last from top to bottom
//1->2->3->4
System.out.print(n1.data); //to print from top
}
}
9.To check even or odd length.
public void check()
{
Node n1;
n1=head; 1-->2-->3-->4
while(n1!=null && n1.next!=null)
{
n1=n1.next.next; //first 1 second 1-->2-->3 third 1-->2-->3-->4-->null
}
if(n1==null)
{
System.out.print("even");
}
else if(n1.next==null)
{
System.out.print("odd");
}
}
Output:
odd
10.merge two sorted linkList.
-->Using recursion time o(n)
Node mergeLists(Node head1, Node head2) {
Node head;
if(head1==null)
{
return head2;
}
if(head2==null)
{
return head1;
}
if(head1.data>=head2.data)
{
head=head2;
head.next=mergeLists(head1,head2.next); //for getting next we are call this again and again
}
else
{
head=head1;
head.next=mergeLists(head1.next,head2); // same like above case
}
return head;
}
-->without recursion
11.check String is palindrome or not.
method -1 reverse the linklist and compare one by one but its take 2 traversal
Method-2 use stack and using slow and fast algo push the element till middle and after that if length is odd then skip middle and then pop and match from slow data with this move slow also...
public void check()
{
Stack s=new Stack();
Node n1,n2;
n1=n2=head;
int i=0;
while(n1!=null && n1.next!=null)
{
if(i==0)
{
n1=n1.next; //fast
i=1;
}
else if(i==1)
{
n1=n1.next;
s.push(n2.data);
n2=n2.next; //slow
i=0;
}
}
if(n1!=null) //if odd length
{
n2=n2.next;
}
while(n2!=null)
{
int d1=(int)s.pop(); //now poping
if(d1==n2.data) //and checking with slow data u cant check with node bcz two different node kept different address
{
n2=n2.next;
}
else
{
System.out.print("No"); //if not match
break;
}
}
if(s.isEmpty()) //if stack is empty then every thing is fine
{
System.out.print("yes");
}
}
12.swap in pairs
public void swap()
{
Node curr=head;
int data;
int datanext;
while(curr!=null && curr.next!=null)
{
/*Node temp=curr.next;
curr.next=prev;
prev=curr;
curr=temp;
curr=curr.next;
*/
data=curr.data; //storing current data
datanext=curr.next.data; // storing next data
//swapping
int temp=data;
curr.data=datanext;
curr.next.data=temp;
curr=curr.next.next;
}
}
13.add two number
public ListNode addTwoNumbers(ListNode l1, ListNode l2)
{
ListNode newnode=new ListNode(0);
int carry=0;
ListNode p1=l1,p2=l2,p3=newnode;
while(p1!=null || p2!=null)
{
if(p1!=null)
{
carry=carry+p1.val;
p1=p1.next;
}
if(p2!=null)
{
carry=carry+p2.val;
p2=p2.next;
}
p3.next=new ListNode(carry%10);
p3=p3.next;
carry=carry/10;
}
if(carry>0)
p3.next=new ListNode(carry);
return newnode.next;
}
14. Intersection point of two linkList
public ListNode getIntersectionNode(ListNode headA, ListNode headB)
{
ListNode a = headA;
ListNode b = headB;
while (a != null || b != null)
{
if (a != null)
{
a = a.next;
}
else
{
headB = headB.next;
}
if (b != null)
{
b = b.next;
}
else
{
headA = headA.next;
}
}
while (headA != headB)
{
headA = headA.next;
headB = headB.next;
}
return headA;
}
Stack in java
1. Object push(Object element) : Pushes an element on the top of the stack.
2. Object pop() : Removes and returns the top element of the stack. An ‘EmptyStackException’ exception is thrown if we call pop() when the invoking stack is empty.
3. Object peek( ) : Returns the element on the top of the stack, but does not remove it.
4. boolean empty() : It returns true if nothing is on the top of the stack. Else, returns false.
5. int search(Object element) : It determines whether an object exists in the stack. If the element is found, it returns the position of the element from the top of the stack. Else, it returns -1.
Queue in java
boolean add(object): It is used to insert the specified element into this queue and return true upon success.
boolean offer(object):It is used to insert the specified element into this queue.
Object remove():It is used to retrieves and removes the head of this queue.
Object poll():It is used to retrieves and removes the head of this queue, or returns null if this queue is empty.
Object element():It is used to retrieves, but does not remove, the head of this queue. Object peek():It is used to retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.
Note:
System.out.println("iterating the queue elements:");
Iterator itr=queue.iterator();
while(itr.hasNext())
{
System.out.println(itr.next());
}
Vector in java
void add(int index, Object element)
Inserts the specified element at the specified position in this Vector.
boolean add(Object o)
Appends the specified element to the end of this Vector.
boolean equals(Object o)
Compares the specified Object with this vector for equality.
Object firstElement()
Returns the first component (the item at index 0) of this vector.
boolean isEmpty()
Tests if this vector has no components.
Object lastElement()
Returns the last component of the vector.
Object remove(int index)
Removes the element at the specified position in this vector.
boolean remove(Object o)
Removes the first occurrence of the specified element in this vector, If the vector does not contain the element, it is unchanged.
int size()
Returns the number of components in this vector.
Hashset
add(A)
Adds the specified element to this HashSet if it is not already present.
Removes all of the elements from this HashSet.
Returns a shallow copy of this HashSet
Returns true if this HashSet contains the specified element.
Returns true if this HashSet contains no elements.
Returns an Iterator over the elements in this HashSet
Removes the given element from this HashSet if it is present.
Returns the number of elements in this HashSet (its cardinality).
Java HashMap class
MethodDescription
void clear():It is used to remove all of the mappings from this map.
boolean containsKey(Object key):It is used to return true if this map contains a mapping for the specified key.
boolean containsValue(Object value):It is used to return true if this map maps one or more keys to the specified value.
boolean isEmpty():It is used to return true if this map contains no key-value mappings.
Object clone():It is used to return a shallow copy of this HashMap instance: the keys and values themselves are not cloned.
Set entrySet():It is used to return a collection view of the mappings contained in this map.
Set keySet():It is used to return a set view of the keys contained in this map.
Object put(Object key, Object value):It is used to associate the specified value with the specified key in this map.
int size():It is used to return the number of key-value mappings in this map.
Collection values():It is used to return a collection view of the values contained in this map.
HashMap<String, Integer> map = new HashMap<>();
print(map);
map.put("vishal", 10);
map.put("sachin", 30);
map.put("vaibhav", 20);
System.out.println("Size of map is:- " + map.size());
print(map);
if (map.containsKey("vishal"))
{
Integer a = map.get("vishal");
System.out.println("value for key \"vishal\" is:- " + a);
}
15.Rotate LinkKList k times
class Solution
{
public ListNode rotateRight(ListNode head, int n) {
if (head==null||head.next==null) return head;
ListNode dummy=new ListNode(0);
dummy.next=head;
ListNode fast=dummy,slow=dummy;
int i;
for (i=0;fast.next!=null;i++)//Get the total length
fast=fast.next;
for (int j=i-n%i;j>0;j--) //Get the i-n%i th node
slow=slow.next;
fast.next=dummy.next; //Do the rotation
dummy.next=slow.next;
slow.next=null;
return dummy.next;
}
}
16.Remove all Duplicates from Sorted List
Input: 1->2->3->3->4->4->5
Output: 1->2->5
Output: 1->2->5
class Solution
{
public ListNode deleteDuplicates(ListNode head)
{
if(head==null || head.next==null)
{
return head;
}
ListNode n1=new ListNode(0);
n1.next=head;
ListNode p=n1;
while(p.next!=null && p.next.next!=null )
{
if(p.next.next.val!=p.next.val)
{
p=p.next;
continue;
}
while(p.next.next!=null && p.next.next.val==p.next.val)
{
p.next.next=p.next.next.next;
}
p.next=p.next.next;
}
return n1.next;
}
}
17.Odd Even Linked List
Given 1->2->3->4->5->NULL,
return 1->3->5->2->4->NULL.
return 1->3->5->2->4->NULL.
class Solution
{
public ListNode oddEvenList(ListNode head)
{
if(head==null)
{
return head;
}
ListNode result=head;
ListNode p1=head;
ListNode p2=head.next;
ListNode connectnode=head.next;
while(p1!=null && p2!=null)
{
ListNode t=p2.next;
if(t==null)
{
break;
}
p1.next=p2.next;
p1=p1.next;
p2.next=p1.next;
p2=p2.next;
}
p1.next=connectnode;
return result;
}
}
18.Reverse Linked List from mth to nth position
Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL
Output: 1->4->3->2->5->NULL
- Find start of sub-list to reverse
- Reverse sub-list
- Re-map reversed sub-list head and tail to the main list
class Solution {
public ListNode reverseBetween(ListNode head, int m, int n)
{
ListNode offlist=new ListNode(0);
offlist.next=head;
ListNode b = offlist;
for(int i=1;i<m;i++)
{
b=b.next;
}
ListNode prev=b.next;
ListNode curr=prev.next;
for(int i=m;i<n;i++)
{
ListNode temp=curr.next;
curr.next=prev;
prev=curr;
curr=temp;
}
ListNode t=b.next;
b.next=prev;
t.next=curr;
return offlist.next;
}
}
19.reorder link list
Given a singly linked list L0 -> L1 -> … -> Ln-1 -> Ln. Rearrange the nodes in the list so that the new formed list is : L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 …
Given 1->2->3->4, reorder it to 1->4->2->3.
class Solution
{
public ListNode reverse(ListNode root)
{
ListNode prev=null,curr=root;
while(curr!=null)
{
ListNode temp=curr.next;
curr.next=prev;
prev=curr;
curr=temp;
}
return prev;
}
public void reorderList(ListNode head)
{
if(head==null)
{
return;
}
// step1:find middle node
ListNode slow=head;
ListNode fast=head.next;
while(slow!=null && fast!=null && fast.next!=null)
{
slow=slow.next;
fast=fast.next.next;
}
//step2:till here we got middle node now break link list in two part
ListNode node1=head;
ListNode node2=slow.next;
slow.next=null; //putting middle.next=null
//step3:reverse linklist after middle node and create new link list with
node2 as root of new LL
node2=reverse(node2);
ListNode node=new ListNode(0); // creted dummy link list
ListNode curr=node;
//step4:created and update new linklist and get desired pattern
while(node1!=null || node2!=null)
{
if(node1!=null)
{
curr.next=node1;
curr=curr.next;
node1=node1.next;
}
if(node2!=null)
{
curr.next=node2;
curr=curr.next;
node2=node2.next;
}
}
head=node.next;
}
}
20.merge sort of a linklist
class Solution
{
//method to get middle node
public ListNode getMiddle(ListNode head)
{
ListNode slow=head;
ListNode fast=head.next;
while(slow!=null && fast!=null && fast.next!=null)
{
slow=slow.next;
fast=fast.next.next;
}
return slow;
}
//method to merge two sorted linklist
ListNode sortMerge(ListNode left,ListNode right)
{
ListNode result=null;
if(left==null)
{
return right;
}
if(right==null)
{
return left;
}
if(left.val<=right.val)
{
result=left;
result.next=sortMerge(left.next,right);
}
else
{
result=right;
result.next=sortMerge(left,right.next);
}
return result;
}
public ListNode insertionSortList(ListNode head)
{
if(head==null || head.next==null)
{
return head;
}
//step1:
ListNode middle=getMiddle(head); // get middle node
ListNode nextOfMiddle=middle.next;
middle.next=null; //divide the link list into left and right part
ListNode left= insertionSortList(head);//recursive call left part
ListNode right=insertionSortList(nextOfMiddle);//recursive call right part
//step 2: merge the left and right part
ListNode sorted=sortMerge(left,right);
return sorted;
}
}
21.Remove Linked List Elements
Input: 1->2->6->3->4->5->6, val = 6
Output: 1->2->3->4->5
Output: 1->2->3->4->5
class Solution
{
public ListNode removeElements(ListNode head, int val)
{
ListNode dummy=new ListNode(0);
dummy.next=head;
ListNode curr=dummy;
while(curr.next!=null)
{
if(curr.next.val==val)
{
curr.next=curr.next.next; //if equal ,move two next pointer
}
else
{
curr=curr.next;
}
}
return dummy.next;
}
}
Comments
Post a Comment