Sunday 15 March 2015

Given a singly linked list swap every two nodes

Java program to swap every two nodes in a LinkedList e.g. 1->2->3->4->5->6 should become 2->1->4->3->6->5
/**
 * @author vikky.agrawal
 */

public class LinkedList {

	Node node = null;
	

	public static void main(String[] args) {

		LinkedList list = new LinkedList();
		list.operations();

	}

	public void operations() {

		this.node = new Node(10);

		for (int i = 1; i < 6; i++) {
			add(node, (int) (Math.random() * 100));
		}
		this.swap(node);
	}
	
	/**
	 * Given a singly linked list, swap every two nodes
	 * e.g. 1->2->3->4->5->6 should become 2->1->4->3->6->5
	 */
	
	public void swap(Node root){
		
		if(root == null){
			return;
		}
		
		System.out.println("before swap : ");
		print(root);
		
		
		Node temp=root;
		while(temp!=null && temp.getLink()!=null){
			int data=temp.getData();
			temp.setData(temp.getLink().getData());
			temp.getLink().setData(data);
			temp=temp.getLink().getLink();
		}
		System.out.println("After swap");
		print(root);
		
	}
	
	
	/**
	 * Helper functions for LinkedList
	 */
	public void add(Node ptr, int data) {
		if (ptr == null) {
			System.out.println("Always null ?");
			ptr = new Node(data);
		} else {
			Node newptr = ptr;
			while (newptr.getLink() != null) {
				newptr = newptr.getLink();
			}
			newptr.setLink(new Node(data));
			newptr.getLink().setLink(null);
		}
	}

	public void print(Node ptr) {

		if (ptr == null) {
			return;
		}
		Node ptr1 = ptr;
		System.out.print(ptr1.getData() + "->");
		while ((ptr1 = ptr1.getLink()) != null) {
			System.out.print(ptr1.getData() + "->");
		}
		System.out.println("/n");

	}

	public int size(Node ptr) {

		if (ptr == null) {
			return -1;
		}
		Node ptr1 = ptr;
		int i = 1;
		while ((ptr1 = ptr1.getLink()) != null) {
			i++;
		}
		return i;
	}
	
	/**
	 * static inner class for LinkedList Data Structure
	 */
	private static class Node{
		 private int data;
		 private Node link; 		 
		    
		    Node(){
		    	    	
		    }
		    
		    Node(int data){
		    	//mergedList=new Node();
		        this.setData(data);
		        this.setLink(null);       
		    }
		    
		    public int getData(){
		        return this.data;
		    }
		      
		    public Node getLink(){
		        return this.link;
		    }
		    
		    public void setData(int data){
		        this.data=data;
		    }       
		    
		    public void setLink(Node link){
		        this.link=link;
		    }  
	}
	
}

No comments:

Post a Comment