Implement Queue using doubly linkedlist

// Implementation of Queue using doubly linkedlist


class QNode{
 int val;
 QNode next, prev;
 
 public QNode(int val)
 {
  this.val = val;
  this.next = this.prev = null;
 }
 
}

class Queue{
 
 private QNode front, rear, middle;
 private int count;

 void enqueue(int d)
 {
  QNode node = new QNode(d);
  count++;
  if(isEmpty())
  {
   front = rear = middle = node;
  }else{
   rear.next = node;
   node.prev = rear;
   rear = rear.next;
   if((count&1) == 1) middle = middle.next;
   
  }
   
 }
 
 
 int dequeue()
 {
  int r = -1;
  if(!isEmpty())
  {
   if(front == rear)
   {
    r = front.val;
    front = rear = middle = null;
    count--;
   }else{
    r = front.val;
    front = front.next;
    count--;
   }
   
   if((count & 1) != 0 && middle != null) 
   {
    middle = middle.next;
    }
  }
  return r;
 }
 
 int middleElement()
 {
  if(!isEmpty())
   return middle.val;
  return -1;
 }
 
 void deleteElement()
 {
  
  if(middle.prev == null && front != null)
  {
   System.out.println("Deleted:"+middle.val);
   front = front.next;
   if(front != null){
    front.prev = null;
    middle = front;
   }
   count--;
  }else     
  if(middle != null)
  {
   System.out.println("Deleted:"+middle.val);
   middle.prev.next = middle.next;
   middle.next.prev = middle.prev;
   count--;
   if((count & 1) != 0 && middle != null) //odd
   {
    middle = middle.next;
   }else
   {
    middle = middle.prev;
   }
  }
 }
 
 
 boolean isEmpty()
 {
  if(front == null) return true;
  return false;
 }
 
 
 public static void main(String args[])
 {
  Queue q = new Queue();
  q.enqueue(2);
  q.enqueue(5);
  q.enqueue(6);
  q.enqueue(8);
  
  //System.out.println(q.middleElement());
  q.deleteElement();
  q.deleteElement();
  q.deleteElement();
  q.deleteElement();
  System.out.println(q.middleElement());
 }
 
}

Merge a linked list into another linked list at alternate positions

// Merging Two list into single List

 public static ListNode mergeList(ListNode h1, ListNode h2)
 {
  if(h1==null && h2 == null) return null;
  ListNode c1,c2, t1,t2;
  for(c1 = h1, c2 = h2; c1!=null && c2!=null; )
  {
   t1 = c1.next;
   t2 = c2.next;
   
   c2.next = c1.next;
   c1.next = c2;
   
   c1 = t1;
   c2 = t2;
  }
  
  if(c1 == null)
   h2 = c2;
  else
   h2 = null;
   
  return h2;
 }

Pairwise swap/ k elements of a given linked list by changing links

// Comment  Pairwise swaping

 public static LNode altReverse(LNode list){
  
  if(list == null || list.next == null) return list;
  
  LNode oldHead = list;
  
  LNode head = altReverse(list.next.next);
  
  LNode tmp = oldHead.next;
  oldHead.next = head;
  tmp.next = oldHead;
  
  return tmp;
 } 

// Comment  swaping  k elements of a given linked list

 public static LNode altReverse(LNode list, int k) {

  if (list == null)
   return list;

  LNode oldHead = list;
  int i = k;
  while (list != null && i > 0) {
   list = list.next;
   i--;
  }

  LNode head = altReverse(list, k);

  int j = k;
  LNode curr = oldHead, prev = null;
  while (curr != null && j > 0 && i == 0) {
   LNode next = curr.next;
   curr.next = prev;
   prev = curr;
   curr = next;
   j--;
  }

  if (i != 0)
   return oldHead;
  else {
   oldHead.next = head;
   return prev;
  }

 }

LinkedList isPalindrome or not - Java

Implementation:

Or Using Extra space- stack:

:

Delete N nodes after M nodes of a linked list

Java Implementation:

static listNode deleteMNodeAfterN(listNode head, int M, int N){
if(head == null) return head;

listNode curr = head, next = head;


while(next != null){

for(int i = 0 ; curr != null && i < M-1; i++)
curr = curr.next;
if(curr == null) return head;

next = curr;
for(int i = 0; next != null && i < N; i++)
next = next.next;
if(next == null)
{
curr.next = null;
return head;
}
curr.next = next.next;
curr = curr.next;
}
return head;
}


Reference:
http://www.geeksforgeeks.org/delete-n-nodes-after-m-nodes-of-a-linked-list/

You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1 's digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list. FOLLOW UP Suppose the digits are stored in forward order. Repeat the above problem.

static LNode addTwoList(LNode l1, LNode l2){

if(l1 == null) return l2;
if(l2 == null) return l1;

int sum = 0, carry = 0;
LNode l = null, head = null;
for(; l1 != null || l2 != null; )
{
sum = carry;
if(l1 != null){
sum = sum + l1.val;
l1 = l1.next;
}
if(l2 != null){
sum = sum + l2.val;
l2 = l2.next;
}
carry = sum / 10;

if(l == null){
l = new LNode(sum%10);
head = l;
}
else {
l.next = new LNode(sum%10);
l = l.next;
}
sum = 0;
}

if(carry > 0)
{
l.next = new LNode(carry);
}
return head;
}








SOLUTION
It's useful to remember in this problem how exactly addition works. Imagine the
problem:
6 1 7
+ 2 9 5
First, we add 7 and 5 to get 12. The digit 2 becomes the last digit of the number, and 1
gets carried over to the next step. Second, we add 1,1, and 9 to get 11 .The 1 becomes
the second digit, and the other 1 gets carried over the final step. Third and finally, we
add 1,6 and 2 to get 9. So, our value becomes 912.
We can mimic this process recursively by adding node by node, carrying over any
"excess"data to the next node. Let's walkthrough this for the below linked list:
7 -> 1 -> 6
+ 5 -> 9 -> 2
We do the following:
1. We add 7 and 5 first, getting a result of 12.2 becomes the first node in our linked list
and we "carry" the 1 to the next sum.
List: 2 -> ?
2. We then add 1 and 9, as well as the "carry," getting a result of 11. 1 becomes the
second element of our linked list, and we carry the 1 to the next sum.
List: 2 -> 1 -> ?
3. Finally, we add 6, 2 and our "carry," to get 9. This become the final element of our
linked list.
List: 2 -> 1 -> 9.
The code below implements this algorithm.
1 LinkedListNode addLists(LinkedListNode 11, LinkedListNode 12,
2 int carry) {
3 /* We're done if both lists are null AND the carry value is 0 */
4 if (11 == null && 12 == null && carry == 0) {
5 return null;
6 }
7
8 LinkedListNode result = new LinkedListNode(carry, null, null);
9
10 /* Add value, and the data from 11 and 12 */
11 int value = carry;
12 if (11 != null) {
13 value += 11.data;
14 }
15 if (12 != null) {
16 value += 12.data;
17 }
18
19 result.data = value % 10; /* Second digit of number */
20
21 /* Recurse */
if (11 != null || 12 != null) {
23 LinkedListNode more = addLists(ll == null ? null : 11.next,
24 12 == null ? null : 12.next,
25 value >= 10 ? 1 : 8);
26 result.setNext(more);
}
28 return result;
29 }
In implementing this code, we must be careful to handle the condition when one linked
list is shorter than another. We don't want to get a null pointer exception.

Pairwise swap elements of a given linked list by changing links

// Head of linkedlist has to change for pairwise swap and returns head of linkedlist.

Method #1.

static listNode pairwiseSwap(listNode head)
{
if(head == null || head.next == null) return head;
listNode curr, tmp, oldhead;
// Initial swap of two nodes
oldhead = head;

tmp = head.next;
head = tmp;
//head = head.next;
oldhead.next = oldhead.next.next;
tmp.next = oldhead;


for(curr = oldhead.next; curr != null && curr.next != null; curr = curr.next)
{
tmp = curr.next;
curr.next = curr.next.next;
tmp.next = curr;
oldhead.next = tmp;
oldhead = curr;
}
return head;
}


Method #2.

static listNode swapPairWise(listNode head){
if(head == null || head.next == null) return head;

listNode curr = head;

if(head.next.next == null)
{

head = curr.next;
head.next = curr;
curr.next = null;
}else{

listNode next = curr.next.next;
head = curr.next;
head.next = curr;
listNode tail = head.next;
tail.next = null;

while(next != null && next.next != null)
{
curr = next;
next = next.next.next;
curr.next.next = curr;
tail.next = curr.next;
tail = curr;
tail.next = null;
}
if(next != null && next.next == null)
tail.next = next;
}


return head;
}

Method #3.

static listNode swapRecursive(listNode head){
if(head == null || head.next == null) return head;

listNode next= head.next.next, newhead = head.next;
head.next.next = head;
head.next = swapPairWise(next);

return newhead;
}

References:
http://www.geeksforgeeks.org/pairwise-swap-elements-of-a-given-linked-list-by-changing-links/