Swapping two nodes

Given a linked list and two characters to swap ,
WE NEED TO SWAP TWO NODES NOT THE VALUES given.

Algorithm
step 1- start traversing the linked list
step 2- assign the nodes which contain the given values as t1 and t2.respectively
step 3- assign the previous nodes before the nodes contain the given values as p1 and p2
step 4-assign p1 next node to t2
step 5-assign p2 next node to t1
step 6-assign t1 next node to t2 next node
step 7-at last assign assign t2 next node to p2
step 8-end

For example
the given linked list be
1->2->3->4->5->null

swap 3 and 5

according to the algorithm
p1 node will be 2
t1 node will be 3
p2 node will be 4
t2 node will be 5

then while we execute the below code
        p1.next=t2;
        p2.next=t1;
        t1.next=t2.next;
        t2.next=p2;
the nodes get swapped.

output will be 1->2->5->4->3->null

Code
public class Loop {

        static class Node
    {
        char data;
        Node next;
        Node(char data)
        {
            this.data=data;
            next=null;
        }
    }

    Node head=null;  

public void display(Node head)
    {
        Node temp=head;
        while(temp!=null)
        {
            System.out.print(temp.data +"->");
            temp=temp.next;
        }
    }
    public void swap(char a,char b,Node head)
    {
        Node temp=head;
        Node p1=null,t1=null,p2=null,t2=null;
        while (temp!=null)
        {
            if(temp.data==a)
            {
                t1=temp;
                break;
            }
            temp=temp.next;
        }
        temp=head;
        while (temp!=null)
        {
            if(temp.data==b)
            {
                t2=temp;
                break;
            }
            temp=temp.next;
        }
        temp=head;
        while (temp.next!=t1)
        {
            temp=temp.next;
        }
        p1=temp;
        temp=head;
        while (temp.next!=t2)
        {
            temp=temp.next;
        }
        p2=temp;
        p1.next=t2;
        p2.next=t1;
        t1.next=t2.next;
        t2.next=p2;
        System.out.println("");
        display(head);
    }
    public static void main(String[] args)
    {
        Loop lp=new Loop();
        lp.head=new Node('1');
        lp.head.next=new Node('2');
        lp.head.next.next=new Node('3');
        lp.head.next.next.next=new Node('4');
        lp.head.next.next.next.next=new Node('5');
        lp.head.next.next.next.next.next=new Node('6');
        lp.display(lp.head);
        lp.swap('3', '5', lp.head);
   }
}

 OUTPUT

 1->2->3->4->5->6->

1->2->5->4->3->6->BUILD SUCCESSFUL (total time: 0 seconds)

Comments

Post a Comment

Popular posts from this blog

Female co passenger hack

The female co-passenger hack. I came across this trick on the internet. When you need to book a ticket on IRCTC (Indian Railways), book two seats instea of one, and cancel one after some days. One in your name and one in fake Female name to get a girls in the compartment. The IRCTC algorithm works that way.
Read more

C library function - qsort()

Image
Description               The C library function void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*)) sorts an array. Parameters base -- This is the pointer to the first element of the array to be sorted. nitems -- This is the number of elements in the array pointed by base. size -- This is the size in bytes of each element in the array. compar -- This is the function that compares two elements. Return Value This function does not return any value Code   #include <stdio.h> #include <stdlib.h> int values [] = { 88 , 56 , 100 , 2 , 25 }; int cmpfunc ( const void * a , const void * b ) { return ( *( int *) a - *( int *) b ); } int main () { int n ; printf ( "Before sorting the list is: \n" ); for ( n = 0 ; n < 5 ; n ++ ) { printf ( "%d " , values [ n ]); } qsort (...
Read more

Wildcard Pattern Matching (DP)

Given a text and a wildcard pattern, implement wildcard pattern matching algorithm that finds if wildcard pattern is matched with text. The matching should cover the entire text (not partial text). The wildcard pattern can include the characters ‘?’ and ‘*’ ‘?’ – matches any single character ‘*’ – Matches any sequence of characters (including the empty sequence) Text = "baaabab", Pattern = “*****ba*****ab", output : true Pattern = "baaa?ab", output : true Pattern = "ba*a?", output : true Pattern = "a*ab", output : false Each occurrence of ‘?’ character in wildcard pattern can be replaced with any other character and each occurrence of ‘*’ with a sequence of characters such that the wildcard pattern becomes identical to the input string after replacement. Let’s consider any character in the pattern. Case 1: The character is ‘*’ Here two cases arise We can ignore ‘*’ character and move to next character in the Pattern. ‘*’ cha...
Read more