LinkedList
Remove Nth Node From End of List
Given the head of a linked list, remove the nth node from the end of the list and return its head.
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
Example 2:
Input: head = [1], n = 1
Output: []
Example 3:
Input: head = [1,2], n = 1
Output: [1]
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution
{
public ListNode removeNthFromEnd(ListNode head, int n)
{
if(head.next==null)
return null;
ListNode slow=head;
ListNode fast=head;
for(int i=1;i<=n;i++)
fast=fast.next;
// edge case handeled when we have to delete the 1st node
// i.e n=size of linked list
if(fast==null)
return head.next;
while(fast!=null && fast.next!=null)
{
fast=fast.next;
slow=slow.next;
}
slow.next=slow.next.next;
return head;
}
}
LinkedList Cycle
/**
* 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 || head.next == null || head.next.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (slow == fast) {
return true;
}
}
return false;
}
}
Delete the Middle Node of a Linked List
You are given the head of a linked list. Delete the middle node,
and return the head of the modified linked list.
Input: head = [1,3,4,7,1,2,6]
Output: [1,3,4,1,2,6]
Explanation: 7 is the middle element
class Solution {
public ListNode deleteMiddle(ListNode head) {
if (head == null || head.next == null) {
return null;
}
if (head.next.next == null) {
head.next = null;
return head;
}
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
slow.val = slow.next.val;
slow.next = slow.next.next;
return head;
}
}Delete the Middle Node of a Linked List
You are given the head of a linked list. Delete the middle node,
and return the head of the modified linked list.
Input: head = [1,3,4,7,1,2,6]
Output: [1,3,4,1,2,6]
Explanation: 7 is the middle element
class Solution {
public ListNode deleteMiddle(ListNode head) {
if (head == null || head.next == null) {
return null;
}
if (head.next.next == null) {
head.next = null;
return head;
}
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
slow.val = slow.next.val;
slow.next = slow.next.next;
return head;
}
}
Merge two sorted List
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode temp = new ListNode();
ListNode ans = temp;
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
temp.next = list1;
temp = temp.next;
list1 = list1.next;
} else {
temp.next = list2;
temp = temp.next;
list2 = list2.next;
}
}
if (list1 != null) {
temp.next = list1;
}
if (list2 != null) {
temp.next = list2;
}
return ans.next;
}
}
Remove Linked List Elements
Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.
Input: head = [1,2,6,3,4,5,6], val = 6
Output: [1,2,3,4,5]
Example 2:
Input: head = [], val = 1
Output: []
Example 3:
Input: head = [7,7,7,7], val = 7
Output: []
Middle of the Linked List
Given the head of a singly linked list, return the middle node of the linked list.
If there are two middle nodes, return the second middle node.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode middleNode(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
Remove Nth Node From End of List
Given the head of a linked list, remove the nth node from the end of the list and return its head.
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
Example 2:
Input: head = [1], n = 1
Output: []
Example 3:
Input: head = [1,2], n = 1
Output: [1]
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution
{
public ListNode removeNthFromEnd(ListNode head, int n)
{
if(head.next==null)
return null;
ListNode slow=head;
ListNode fast=head;
for(int i=1;i<=n;i++)
fast=fast.next;
// edge case handeled when we have to delete the 1st node
// i.e n=size of linked list
if(fast==null)
return head.next;
while(fast!=null && fast.next!=null)
{
fast=fast.next;
slow=slow.next;
}
slow.next=slow.next.next;
return head;
}
}
Singly LinkedList Implementation
public class Program {
static class Node {
int number;
Node next;
public Node(int number) {
this.number = number;
next = null;
}
}
public static void main( ) {
Node head;
Node first = new Node(10);
Node second = new Node(20);
Node third = new Node(30);
Node fourth = new Node(40);
first.next = second;
second.next = third;
third.next = fourth;
System.out.println("Iterative Printing");
printLinkedList(first);
System.out.println("Recursive Printing");
printLinkedLRecursive(first);
System.out.println("Inserting head");
head = insertHeadLL(0, first);
printLinkedLRecursive(head);
System.out.println("Inserting at end");
head = insertNodeEndLL(50, head);
printLinkedLRecursive(head);
System.out.println("Deleting Head node");
head = deleteHeadNodeLL(head);
printLinkedList(head);
System.out.println("Delete Last node");
head = deleteLastNodeLL(head);
printLinkedLRecursive(head);
System.out.println("Insert data at postion");
head = insertDataAtPos(4, 25, head);
printLinkedLRecursive(head);
System.out.println("Find Data iter : " + searchInLLIter(30, head));
System.out.println("Find Data recur : " + searchInLLRec(60, 1, head));
}
public static void printLinkedList(Node curr) {
while (curr != null) {
System.out.print(curr.number + " ");
curr = curr.next;
}
System.out.println();
}
public static void printLinkedLRecursive(Node curr) {
if (curr == null) {
System.out.println();
return;
}
System.out.print(curr.number + " ");
printLinkedLRecursive(curr.next);
}
public static Node insertHeadLL(int number, Node currHead) {
Node newNode = new Node(number);
newNode.next = currHead;
return newNode;
}
public static Node insertNodeEndLL(int number, Node head) {
Node ptr = head;
if (head == null) {
return insertHeadLL(number, null);
}
// DESIGN
while (ptr.next != null)
ptr = ptr.next;
ptr.next = new Node(number);
return head;
}
public static Node deleteHeadNodeLL(Node head) {
if (head == null) {
return null;
}
return head.next;
}
public static Node deleteLastNodeLL(Node head) {
if (head == null) {
return null;
}
if (head.next == null) {
return null;
}
Node ptr = head;
// DESIGN
while (ptr.next.next != null)
ptr = ptr.next;
ptr.next = null;
return head;
}
public static Node insertDataAtPos(int position, int number, Node head) {
if (position == 1) {
return insertHeadLL(number, head);
}
// *** DESIGN ***
Node ptr = head;
for (int i = 1; i < position - 1 && ptr != null; i++) {
ptr = ptr.next;
}
if (ptr == null) {
return head;
}
Node temp = new Node(number);
temp.next = ptr.next;
ptr.next = temp;
return head;
}
public static int searchInLLIter(int number, Node head) {
Node ptr = head;
int count = 1;
while (ptr != null) {
if (ptr.number == number) {
return count;
}
ptr = ptr.next;
count++;
}
return -1;
}
public static int searchInLLRec(int number, int index, Node head) {
if (head == null) {
return -1;
}
if (head.number == number) {
return index;
}
return searchInLLRec(number, index + 1, head.next);
}
}
Circular LinkedList Implementation
public class Program {
static class Node {
int number;
Node next;
public Node(int number) {
this.number = number;
next = null;
}
}
public static void main( ) {
Node head = new Node(10);
head.next = new Node(20);
head.next.next = new Node(30);
head.next.next.next = new Node(40);
head.next.next.next.next = head;
System.out.println("Printing CLL");
printCLL(head);
System.out.println("Insert Head");
head = insertHead(0, head);
printCLL(head);
System.out.println("Insert tail");
head = insertTail(50, head);
printCLL(head);
System.out.println("delete head");
head = deleteHead(head);
printCLL(head);
System.out.println("delete kth node");
head = deleteKthNode(3, head);
printCLL(head);
}
public static void printCLL(Node head) {
Node ptr = head;
if (head == null) {
return;
}
// DESIGN
do {
System.out.print(ptr.number + " ");
ptr = ptr.next;
} while (ptr != head);
System.out.println();
}
public static Node insertHead(int number, Node head) {
Node temp = new Node(number);
if (head == null) {
temp.next = temp;
return temp;
}
temp.next = head.next;
head.next = temp;
int t = head.number;
head.number = temp.number;
temp.number = t;
return head;
}
public static Node insertTail(int number, Node head) {
Node temp = new Node(number);
if (head == null) {
temp.next = temp;
return temp;
}
temp.next = head.next;
head.next = temp;
int t = temp.number;
temp.number = head.number;
head.number = t;
return temp;
}
public static Node deleteHead(Node head) {
if (head == null || head.next == head) {
return null;
}
int t = head.next.number;
head.next = head.next.next;
head.number = t;
return head;
}
public static Node deleteKthNode(int pos, Node head) {
if (pos == 1) {
return deleteHead(head);
}
Node ptr = head;
for (int i = 0; i < pos - 2; i++) {
ptr = ptr.next;
}
ptr.next = ptr.next.next;
return head;
}
}
Doubly LinkedList Implementation
public class Program {
static class Node {
int number;
Node next;
Node prev;
public Node(int number) {
this.number = number;
this.next = null;
this.prev = null;
}
}
public static void main( ) {
Node head;
Node first = new Node(10);
Node second = new Node(20);
Node third = new Node(30);
Node fourth = new Node(40);
first.next = second;
first.prev = null;
second.next = third;
second.prev = first;
third.prev = second;
third.next = fourth;
fourth.prev = third;
fourth.next = null;
System.out.println("Inserting at the beginning");
head = insertAtTheBegin(0, first);
printLL(head);
System.out.println("Inserting at the End");
head = insertAtTheEnd(50, head);
printLL(head);
System.out.println("Delete Head");
head = deleteHeadDLL(head);
printLL(head);
System.out.println("Delete Last Node ");
head = deleteLastHead(head);
printLL(head);
System.out.println("reversing a DLL");
Node newHead = reverseDLL(head);
printLL(newHead);
}
public static void printLL(Node node) {
if (node == null) {
System.out.println();
return;
}
System.out.print(node.number + " ");
printLL(node.next);
}
public static Node insertAtTheBegin(int number, Node head) {
if (head == null) {
return new Node(number);
}
Node temp = new Node(number);
head.prev = temp;
temp.next = head;
return temp;
}
public static Node insertAtTheEnd(int number, Node head) {
if (head == null) {
return new Node(number);
}
Node ptr = head;
// DESIGN
while (ptr.next != null)
ptr = ptr.next;
Node temp = new Node(number);
ptr.next = temp;
temp.prev = ptr;
return head;
}
public static Node reverseDLL(Node head) {
if (head == null || head.next == null) {
return head;
}
Node prev = null;
Node curr = head;
while (curr != null) {
prev = curr.prev;
curr.prev = curr.next;
curr.next = prev;
curr = curr.prev;
}
return prev.prev;
}
public static Node deleteHeadDLL(Node head) {
if (head == null) {
return head;
}
if (head.next == null) {
return null;
}
head = head.next;
head.prev = null;
return head;
}
public static Node deleteLastHead(Node head) {
if (head == null) {
return head;
}
if (head.next == null) {
return null;
}
Node ptr = head;
while (ptr.next.next != null)
ptr = ptr.next;
ptr.next = null;
return head;
}
}
Insert into sorted Linkedlist
public class Program {
static class Node {
int number;
Node next;
public Node(int number) {
this.number = number;
this.next = null;
}
}
public static void main(String[] args) {
Node first = new Node(10);
first.next = new Node(20);
first.next.next = new Node(30);
first.next.next.next = new Node(40);
Node head = first;
System.out.println("sorted insert");
head = sortedInsert(13, head);
printLL(head);
}
public static void printLL(Node head) {
Node ptr = head;
do {
System.out.print(ptr.number + " ");
ptr = ptr.next;
} while (ptr != null);
System.out.println();
}
public static Node sortedInsert(int number, Node head) {
Node temp = new Node(number);
if (head == null) {
return temp;
}
if (number < head.number) {
temp.next = head;
return temp;
}
Node curr = head;
while (curr.next != null && curr.next.number < number) {
curr = curr.next;
}
temp.next = curr.next;
curr.next = temp;
return head;
}
}
Middle of Linked List
class Program {
static class Node {
int data;
Node next;
Node(int x) {
data = x;
next = null;
}
}
public static void main ( String[] args ) {
Node head = new Node(10);
head.next = new Node(20);
head.next.next = new Node(30);
head.next.next.next = new Node(40);
head.next.next.next.next = new Node(50);
printlist(head);
System.out.print("Position of element in Linked List: ");
printMiddle(head);
}
static void printMiddle(Node head) {
if (head == null) return;
Node slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
System.out.print(slow.data);
}
public static void printlist(Node head) {
Node curr = head;
while (curr != null) {
System.out.print(curr.data + " ");
curr = curr.next;
}
System.out.println();
}
}
Reverse a Linked-list Iteratively
public class Program {
static class Node {
int data;
Node next;
Node(int x) {
data = x;
next = null;
}
}
public static void main(String[] args ) {
Node head = new Node(10);
head.next = new Node(20);
head.next.next = new Node(30);
head.next.next.next = new Node(40);
head.next.next.next.next = new Node(50);
System.out.print("Position of element in Linked List: ");
head = reverseLL(head);
printlist(head);
}
static Node reverseLL(Node head) {
if(head == null || head.next == null) {
return head;
}
Node prev = null;
Node curr = head;
while(curr != null) {
Node next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
public static void printlist(Node head) {
Node curr = head;
while (curr != null) {
System.out.print(curr.data + " ");
curr = curr.next;
}
System.out.println();
}
}
Reverse a linked-list recursively
public class Main {
static class Node {
int number;
Node next;
public Node(int number) {
this.number = number;
this.next = null;
}
}
public static void main(String[] args) {
Node head = new Node(0);
head.next = new Node(10);
head.next.next = new Node(20);
head.next.next.next = new Node(30);
head = reverseLL(head, null);
printLL(head);
}
public static Node reverseLL(Node curr, Node prev) {
if (curr == null) {
return prev;
}
Node next = curr.next;
curr.next = prev;
return reverseLL(next, curr);
}
public static void printLL(Node head) {
Node ptr = head;
while (ptr != null) {
System.out.print(ptr.number + " ");
ptr = ptr.next;
}
}
}
Delete duplicate Item
public class Main {
static class Node
{
int number;
Node next;
public Node(int number)
{
this.number = number;
this.next = null;
}
}
public static void main(String[] args)
{
Node head = new Node(0);
head.next = new Node(10);
head.next.next = new Node(10);
head.next.next.next = new Node(30);
head.next.next.next.next = new Node(30);
System.out.println("Printing : ");
printLL(head);
System.out.println("Deleting : ");
deleteDLL(head);
printLL(head);
}
static void printLL(Node head) {
Node ptr = head;
while(ptr != null) {
System.out.print(ptr.number+" ");
ptr = ptr.next;
}
System.out.println();
}
static void deleteDLL(Node head) {
Node ptr = head;
while(ptr != null && ptr.next != null) {
if (ptr.number == ptr.next.number) {
ptr.next = ptr.next.next;
} else {
ptr = ptr.next;
}
}
}
}
Floyd Detection Algorithm
public class Main {
static class Node {
int data;
Node next;
Node(int x) {
data = x;
next = null;
}
}
public static void main(String args[]) {
Node head = new Node(15);
head.next = new Node(10);
head.next.next = new Node(12);
head.next.next.next = new Node(20);
head.next.next.next.next = head.next;
if (isLoop(head))
System.out.print("Loop found");
else
System.out.print("No Loop");
}
static boolean isLoop(Node head) {
Node slow_p = head, fast_p = head;
while (fast_p != null && fast_p.next != null) {
slow_p = slow_p.next;
fast_p = fast_p.next.next;
if (slow_p == fast_p) {
return true;
}
}
return false;
}
public static void printlist(Node head) {
Node curr = head;
while (curr != null) {
System.out.print(curr.data + " ");
curr = curr.next;
}
System.out.println();
}
}
Detect and remove the loop in Linked List
public class Main {
static class Node {
int data;
Node next;
Node(int x) {
data = x;
next = null;
}
}
public static void main(String args[]) {
Node head = new Node(15);
head.next = new Node(10);
head.next.next = new Node(12);
head.next.next.next = new Node(20);
head.next.next.next.next = head.next;
if (isLoop(head))
System.out.print("Loop found");
else
System.out.print("No Loop");
}
static boolean isLoop(Node head) {
Node slow_p = head, fast_p = head;
while (fast_p != null && fast_p.next != null) {
slow_p = slow_p.next;
fast_p = fast_p.next.next;
if (slow_p == fast_p) {
return true;
}
}
return false;
}
public static void printlist(Node head) {
Node curr = head;
while (curr != null) {
System.out.print(curr.data + " ");
curr = curr.next;
}
System.out.println();
}
}
Delete node with only pointer given to it
class Main {
static class Node {
int data;
Node next;
Node(int x) {
data = x;
next = null;
}
}
public static void main(String args[]) {
Node head = new Node(10);
head.next = new Node(20);
Node ptr = new Node(30);
head.next.next = ptr;
head.next.next.next = new Node(40);
head.next.next.next.next = new Node(25);
printlist(head);
deleteNode(ptr);
printlist(head);
}
static void deleteNode(Node ptr) {
Node temp = ptr.next;
ptr.data = temp.data;
ptr.next = temp.next;
}
public static void printlist(Node head) {
Node curr = head;
while (curr != null) {
System.out.print(curr.data + " ");
curr = curr.next;
}
System.out.println();
}
}
Segregate even & odd nodes in Linked List
public class Main {
static class Node {
int data;
Node next;
Node(int x) {
data = x;
next = null;
}
}
public static void main(String args[]) {
Node head = new Node(17);
head.next = new Node(15);
head.next.next = new Node(8);
head.next.next.next = new Node(12);
head.next.next.next.next = new Node(10);
head.next.next.next.next.next = new Node(5);
head.next.next.next.next.next.next = new Node(4);
printlist(head);
head = segregate(head);
printlist(head);
}
static Node segregate(Node head) {
Node eS = null, eE = null, oS = null, oE = null;
for (Node curr = head; curr != null; curr = curr.next) {
int x = curr.data;
if (x % 2 == 0) {
if (eS == null) {
eS = curr;
eE = eS;
} else {
eE.next = curr;
eE = eE.next;
}
} else {
if (oS == null) {
oS = curr;
oE = oS;
} else {
oE.next = curr;
oE = oE.next;
}
}
}
if (oS == null || eS == null)
return head;
eE.next = oS;
oE.next = null;
return eS;
}
public static void printlist(Node head) {
Node curr = head;
while (curr != null) {
System.out.print(curr.data + " ");
curr = curr.next;
}
System.out.println();
}
}
Intersection of two linked-list
class Main {
static Node headA, headB;
static class Node {
int data;
Node next;
Node(int d) {
data = d;
next = null;
}
}
int getNode() {
int c1 = getCount(headA);
int c2 = getCount(headB);
int d;
if (c1 > c2) {
d = c1 - c2;
return _getIntesectionNode(d, headA, headB);
} else {
d = c2 - c1;
return _getIntesectionNode(d, headB, headA);
}
}
int _getIntesectionNode(int d, Node node1, Node node2) {
int i;
Node current1 = node1;
Node current2 = node2;
for (i = 0; i < d; i++) {
if (current1 == null) {
return -1;
}
current1 = current1.next;
}
while (current1 != null && current2 != null) {
if (current1.data == current2.data) {
return current1.data;
}
current1 = current1.next;
current2 = current2.next;
}
return -1;
}
int getCount(Node node) {
Node current = node;
int count = 0;
while (current != null) {
count++;
current = current.next;
}
return count;
}
public static void main(String[] args) {
Main list = new Main();
list.headA = new Node(3);
list.headA.next = new Node(6);
list.headA.next.next = new Node(9);
list.headA.next.next.next = new Node(15);
list.headA.next.next.next.next = new Node(30);
list.headB = new Node(10);
list.headB.next = new Node(15);
list.headB.next.next = new Node(30);
System.out.println(list.getNode());
}
}
Pairwise swap in linked-list
class Main {
static class Node {
int data;
Node next;
Node(int x) {
data = x;
next = null;
}
}
public static void main(String args[]) {
Node head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(4);
head.next.next.next.next = new Node(5);
printlist(head);
head = pairwiseSwap(head);
printlist(head);
}
static Node pairwiseSwap(Node head) {
if (head == null || head.next == null)
return head;
Node curr = head.next.next;
Node prev = head;
head = head.next;
head.next = prev;
while (curr != null && curr.next != null) {
prev.next = curr.next;
prev = curr;
Node next = curr.next.next;
curr.next.next = curr;
curr = next;
}
prev.next = curr;
return head;
}
public static void printlist(Node head) {
Node curr = head;
while (curr != null) {
System.out.print(curr.data + " ");
curr = curr.next;
}
System.out.println();
}
}
Clone a linked list using a random pointer
import java.util.HashMap;
class Main {
static class Node {
int data;
Node next, random;
Node(int x) {
data = x;
next = random = null;
}
}
public static void print(Node start) {
Node ptr = start;
while (ptr != null) {
System.out.println("Data = " + ptr.data + ", Random = " + ptr.random.data);
ptr = ptr.next;
}
}
public static Node clone(Node head) {
HashMap<Node, Node> hm = new HashMap<Node, Node>();
for (Node curr = head; curr != null; curr = curr.next)
hm.put(curr, new Node(curr.data));
for (Node curr = head; curr != null; curr = curr.next) {
Node cloneCurr = hm.get(curr);
cloneCurr.next = hm.get(curr.next);
cloneCurr.random = hm.get(curr.random);
}
Node head2 = hm.get(head);
return head2;
}
public static void main(String[] args) {
Node head = new Node(10);
head.next = new Node(5);
head.next.next = new Node(20);
head.next.next.next = new Node(15);
head.next.next.next.next = new Node(20);
head.random = head.next.next;
head.next.random = head.next.next.next;
head.next.next.random = head;
head.next.next.next.random = head.next.next;
head.next.next.next.next.random = head.next.next.next;
System.out.print("Original list : \n");
print(head);
System.out.print("\nCloned list : \n");
Node cloned_list = clone(head);
print(cloned_list);
}
}
Clone linked-list using random pointer without hashing
public class Main {
static class Node {
int data;
Node next, random;
Node(int x) {
data = x;
next = random = null;
}
}
public static void print(Node start) {
Node ptr = start;
while (ptr != null) {
System.out.println("Data = " + ptr.data + ", Random = " + ptr.random.data);
ptr = ptr.next;
}
}
public static Node clone(Node head) {
Node next, temp;
for (Node curr = head; curr != null;) {
next = curr.next;
curr.next = new Node(curr.data);
curr.next.next = next;
curr = next;
}
for (Node curr = head; curr != null; curr = curr.next.next) {
curr.next.random = (curr.random != null) ? (curr.random.next) : null;
}
Node original = head, copy = head.next;
temp = copy;
while (original != null && copy != null) {
original.next = original.next != null ? original.next.next : original.next;
copy.next = copy.next != null ? copy.next.next : copy.next;
original = original.next;
copy = copy.next;
}
return temp;
}
public static void main(String[] args) {
Node head = new Node(10);
head.next = new Node(5);
head.next.next = new Node(20);
head.next.next.next = new Node(15);
head.next.next.next.next = new Node(20);
head.random = head.next.next;
head.next.random = head.next.next.next;
head.next.next.random = head;
head.next.next.next.random = head.next.next;
head.next.next.next.next.random = head.next.next.next;
System.out.print("Original list : \n");
print(head);
System.out.print("\nCloned list : \n");
Node cloned_list = clone(head);
print(cloned_list);
}
}
LRU ( least recently used ) Cache Design
import java.util.*;
import java.io.*;
import java.lang.*;
import java.util.*;
class Node {
int key;
int value;
Node pre;
Node next;
public Node(int key, int value)
{
this.key = key;
this.value = value;
}
}
class LRUCache {
private HashMap<Integer, Node> map;
private int capacity, count;
private Node head, tail;
public LRUCache(int capacity)
{
this.capacity = capacity;
map = new HashMap<>();
head = new Node(0, 0);
tail = new Node(0, 0);
head.next = tail;
tail.pre = head;
head.pre = null;
tail.next = null;
count = 0;
}
public void deleteNode(Node node)
{
node.pre.next = node.next;
node.next.pre = node.pre;
}
public void addToHead(Node node)
{
node.next = head.next;
node.next.pre = node;
node.pre = head;
head.next = node;
}
public int get(int key)
{
if (map.get(key) != null) {
Node node = map.get(key);
int result = node.value;
deleteNode(node);
addToHead(node);
System.out.println("Got the value : " +
result + " for the key: " + key);
return result;
}
System.out.println("Did not get any value" +
" for the key: " + key);
return -1;
}
public void set(int key, int value)
{
System.out.println("Going to set the (key, "+
"value) : (" + key + ", " + value + ")");
if (map.get(key) != null) {
Node node = map.get(key);
node.value = value;
deleteNode(node);
addToHead(node);
}
else {
Node node = new Node(key, value);
map.put(key, node);
if (count < capacity) {
count++;
addToHead(node);
}
else {
map.remove(tail.pre.key);
deleteNode(tail.pre);
addToHead(node);
}
}
}
}
public class TestLRUCache {
public static void main(String[] args)
{
LRUCache cache = new LRUCache(2);
// it will store a key (1) with value
// 10 in the cache.
cache.set(1, 10);
// it will store a key (2) with value 20 in the cache.
cache.set(2, 20);
System.out.println("Value for the key: 1 is " + cache.get(1)); // returns 10
// removing key 2 and store a key (3) with value 30 in the cache.
cache.set(3, 30);
System.out.println("Value for the key: 2 is " +
cache.get(2)); // returns -1 (not found)
// removing key 1 and store a key (4) with value 40 in the cache.
cache.set(4, 40);
System.out.println("Value for the key: 1 is " +
cache.get(1)); // returns -1 (not found)
System.out.println("Value for the key: 3 is " +
cache.get(3)); // returns 30
System.out.println("Value for the key: 4 is " +
cache.get(4)); // return 40
}
}
Merge two sorted linked lists
import java.util.*;
import java.io.*;
import java.lang.*;
class Node {
int data;
Node next;
Node(int x) {
data = x;
next = null;
}
}
class Test {
public static void main(String args[]) {
Node a = new Node(10);
a.next = new Node(20);
a.next.next = new Node(30);
Node b = new Node(5);
b.next = new Node(35);
printlist(sortedMerge(a, b));
}
static Node sortedMerge(Node a, Node b) {
if (a == null)
return b;
if (b == null)
return a;
Node head = null, tail = null;
if (a.data <= b.data) {
head = tail = a;
a = a.next;
} else {
head = tail = b;
b = b.next;
}
while (a != null && b != null) {
if (a.data <= b.data) {
tail.next = a;
tail = a;
a = a.next;
} else {
tail.next = b;
tail = b;
b = b.next;
}
}
if (a == null) {
tail.next = b;
} else {
tail.next = a;
}
return head;
}
public static void printlist(Node head) {
Node curr = head;
while (curr != null) {
System.out.print(curr.data + " ");
curr = curr.next;
}
System.out.println();
}
}
Palindrome linked-list
import java.util.*;
import java.io.*;
import java.lang.*;
class Node {
char data;
Node next;
Node(char x) {
data = x;
next = null;
}
}
class Test {
public static void main(String args[]) {
Node head = new Node('g');
head.next = new Node('f');
head.next.next = new Node('g');
if (isPalindrome(head))
System.out.print("Yes");
else
System.out.print("No");
}
static Node reverseList(Node head) {
if (head == null || head.next == null)
return head;
Node rest_head = reverseList(head.next);
Node rest_tail = head.next;
rest_tail.next = head;
head.next = null;
return rest_head;
}
static boolean isPalindrome(Node head) {
if (head == null)
return true;
Node slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
Node rev = reverseList(slow.next);
Node curr = head;
while (rev != null) {
if (rev.data != curr.data)
return false;
rev = rev.next;
curr = curr.next;
}
return true;
}
}