• Register
Welcome to Developerhelpway Q&A, where you can ask questions and receive answers from other members of the community.

Swap nodes in linked list without swapping its data

0 votes
27 views
Swap two nodes in linked list without swapping its data in java.

Input = [40 80 30 20 10]
Output = [40 20 30 80 10]
asked Sep 18, 2017 in Data Structure And Algorithm by Suresh Dhull

1 Answer

0 votes
See the following running code for swiping two nodes in given linked list:-

package com.ds.linkedlist;

public class Node<T> {

    private T data;
    private Node<T> next;
   
    public Node(){
        setData(null);
        setNext(null);
    }
   
    public Node(T data){
        setData(data);
        setNext(null);
    }
   
    public T getData(){
        return data;
    }
   
    public void setData(T data){
        this.data = data;
    }
   
    public Node<T> getNext(){
        return next;
    }
   
    public void setNext(Node<T> next){
        this.next = next;
    }
   
}

package com.ds.linkedlist;

import java.util.HashMap;

public class SingleLinkedList<T> {
   
    Node<T> head = null;
    Node<T> reverseHead = null;
   
    public void addFirst(T data){
        if(data == null){
            return;
        }
        if(head == null){
            head = new Node<T>(data);
        }else{
            Node<T> newNode = new Node<T>(data);
            newNode.setNext(head);
            head = newNode;
        }
    }   
    /**
    * @param x
    * @param y
    *
    * Swap node x and y in linked list by changing reference
    *
    * Following points to be considered in this program:-
    * 1. Both are not same
    * 2. Both are present in linked list
    * 3. Both are adjacent node
    * 4. Either x or y is head node
    * 5. Either x or y is last node

    */

    public void doSwapNode(T x, T y){
        //Both are same data then no need to swap
        if(x == y){
            return;
        }
        //Find x in list
        Node<T> currX = head, prevX = null;
        while(currX != null && currX.getData() != x){
            prevX = currX;
            currX = currX.getNext();
        }
       
        //Find y in list
        Node<T> currY = head, prevY = null;
        while(currY != null && currY.getData() != y){
            prevY = currY;
            currY = currY.getNext();
        }
       
        //Check either x or y is not exists in list
        if(currX == null || currY == null){
            return;
        }
       
        //x is either head node or other node
        if(prevX == null){
            head = currY; // make head node
        }else{
            prevX.setNext(currY);
        }
        if(prevY == null){
            //make head node
            head = currX;
        }else{
            prevY.setNext(currX);
        }
        //Swap next reference
        Node<T> temp = currX.getNext();
        currX.setNext(currY.getNext());
        currY.setNext(temp);
    }
}

package com.ds.linkedlist;

public class LinkedListTest {

    /**
     * @param args
     */
    public static void main(String[] args) {
        SingleLinkedList<Integer> singleLinkedList = new SingleLinkedList<Integer>();
        singleLinkedList.addFirst(10);
        singleLinkedList.addFirst(20);
        singleLinkedList.addFirst(30);
        singleLinkedList.addFirst(80);
        singleLinkedList.addFirst(40);
        System.out.println("Node List:-");
        singleLinkedList.getNodeData();
        singleLinkedList.doSwapNode(20, 80);
        System.out.println("\nAfter swipe Nodes List:-");
        singleLinkedList.getNodeData();
    }
}

Output:-
Node List:-
40 80 30 20 10
After swipe Nodes List:-
40 20 30 80 10
answered Sep 18, 2017 by ranju_12 (1,740 points)
...