Question

Write a program to swap the first and last elements of a linked list.

(i) by exchanging info part

(ii) through pointers

Need the program in java with no direct usage of packages use node and link.

Answer 1

A program to swap the first and last elements of a linked list

(i) by exchanging info part

class Swap {  // You can also use public keyword before class
      
    //Represent a node of the singly linked list  
    class Node{  
        int data;  
        Node next;  
          
        public Node(int data) {  
            this.data = data;  
            this.next = null;  
        }  
    }  
   
    //Represent the head of the singly linked list  
    public Node head = null;  
      
    //addNode() will add a new node to the list  
    public void addNode(int data) {  
        //Create a new node  
        Node newNode = new Node(data);  
          
        //Checks if the list is empty  
        if(head == null) {  
            //If list is empty, head will point to new node  
            head = newNode;  
        }  
        else {  
            Node current = head;  
            while(current.next != null) {  
                current = current.next;  
            }  
            //newNode will be added after last node of the list  
            current.next = newNode;  
        }  
    }  
      
    //swapLastWithFirst() will swap head node with the last node of the list  
    public void swapLastWithFirst() {  
        Node current = head, temp = null, index = null;  
          
        //If list is empty, then display the list as it is  
        if(head == null) {  
            return;  
        }  
        else {  
            //After the loop, current will point to last element and index will point to second last element  
            while(current.next != null) {  
                index = current;  
                current = current.next;  
            }  
              
            //If list contains only one node, then display list as it is  
            if(head == current) {  
                return;  
            }  
            //If list contains only two nodes, then swap the head node with current node  
            else if(head.next == current) {  
                temp = head;  
                //head will point to last node i.e. current  
                head = current;  
                //node next to new head will be the last node  
                head.next = temp;  
                //Node next to last element will be null  
                temp.next = null;  
            }  
            else {  
                temp = head;  
                //head will point to last node i.e. current  
                head = current;  
                //Detach the list from previous head and add it after new head  
                head.next = temp.next;  
                //Previous head will become last node of the list  
                index.next = temp;  
                //Node next to last element will be null  
                temp.next = null;  
            }  
        }  
    }  
      
    //display() will display all the nodes present in the list  
    public void display() {  
        //Node current will point to head  
        Node current = head;  
        if(head == null) {  
            System.out.println("List is empty");  
            return;  
        }  
        while(current != null) {  
            //Prints each node by incrementing pointer  
            System.out.print(current.data + " ");  
            current = current.next;  
        }  
        System.out.println();  
    }  
      
    public static void main(String[] args) {  
          
        Swap sList = new Swap();  
          
        //Add nodes to the list  
        sList.addNode(1);  
        sList.addNode(2);  
        sList.addNode(3);  
        sList.addNode(4);  
   
        System.out.println("Originals list: ");  
        sList.display();  
          
        //Swaps Last node with first node  
        sList.swapLastWithFirst();  
          
        System.out.println("List after swapping the first node with last: ");  
        sList.display();  
    }  
}  

(ii) through pointers

NOTE:

• Java doesn’t support pointer explicitly, But java uses pointer implicitly: Java use pointers for manipulations of references but these pointers are not available for outside use. Any operations implicitly done by the language are actually NOT visible.

// Java program to exchange  
// first and last node in  
// circular linked list 
class GFG 
{ 
  
static class Node 
{ 
    int data; 
    Node next; 
}; 
  
static Node addToEmpty(Node head,  
                       int data) 
{ 
    // This function is only 
    // for empty list 
    if (head != null) 
    return head; 
  
    // Creating a node dynamically. 
    Node temp = new Node(); 
  
    // Assigning the data. 
    temp.data = data; 
    head = temp; 
  
    // Creating the link. 
    head.next = head; 
  
    return head; 
} 
  
static Node addBegin(Node head, 
                     int data) 
{ 
    if (head == null) 
        return addToEmpty(head, data); 
  
    Node temp = new Node(); 
  
    temp.data = data; 
    temp.next = head.next; 
    head.next = temp; 
  
    return head; 
} 
  
// function for traversing the list  
static void traverse( Node head) 
{ 
    Node p; 
  
    // If list is empty, return. 
    if (head == null) 
    { 
        System.out.print("List is empty."); 
        return; 
    } 
  
    // Pointing to first  
    // Node of the list. 
    p = head; 
  
    // Traversing the list. 
    do
    { 
        System.out.print(p . data + " "); 
        p = p . next; 
  
    } while(p != head); 
} 
  
// Function to exchange  
// first and last node 
static Node exchangeNodes( Node head) 
{ 
    // Find pointer to previous 
    // of last node 
    Node p = head; 
    while (p.next.next != head) 
    p = p.next; 
      
    // Exchange first and last  
    // nodes using head and p 
    p.next.next = head.next; 
    head.next = p.next; 
    p.next = head; 
    head = head.next; 
  
    return head; 
} 
  
// Driver Code 
public static void main(String args[]) 
{ 
    int i; 
    Node head = null; 
    head = addToEmpty(head, 6); 
      
    for (i = 5; i > 0; i--) 
    head = addBegin(head, i); 
    System.out.print("List Before: "); 
    traverse(head); 
    System.out.println(); 
      
    System.out.print("List After: "); 
    head = exchangeNodes(head); 
    traverse(head); 
} 
}