Remove Nth Node from Linked List

Remove 3rd node from below list
Input

Anbu -> Arul -> Arasu-> Bharath-> Catherine -> Davidson

Output

Anbu -> Arul -> Bharath-> Catherine -> Davidson

Idea: Traverse to the Kth Position and point the reference of temp to one next to it. We need to handle one edge case which is when the Kth position is first node then in such case the head should be changed to point temp next position.

public class RemoveNthNodeFromLL {
    public static void main(String[] args) {
        SimpleLinkedList simpleLinkedList = new SimpleLinkedList();

        simpleLinkedList.insertNodeAtEnd("Anbu");
        simpleLinkedList.insertNodeAtEnd("Arul");
        simpleLinkedList.insertNodeAtEnd("Arasu");
        simpleLinkedList.insertNodeAtEnd("Bharath");
        simpleLinkedList.insertNodeAtEnd("Catherine");
        simpleLinkedList.insertNodeAtEnd("Davidson");

        simpleLinkedList.printLinkedList();

        System.out.println("--------------After Removing 3rd Node--------------");

        removeNthNode(simpleLinkedList, 3);

        simpleLinkedList.printLinkedList();
    }


     public static void removeNthNode(SimpleLinkedList simpleLinkedList, Integer indexOfNodeToBeRemoved){
        Node temp = simpleLinkedList.head;

        //Edgecase1 : If Kth index is 1
        if(indexOfNodeToBeRemoved == 1){
            simpleLinkedList.head = temp.next;
            return;
        }

        for(int idx=1;idx<indexOfNodeToBeRemoved-1;idx++){
            temp = temp.next;
        }

        temp.next = temp.next.next;
    }
}

Output

Anbu
Arul
Arasu
Bharath
Catherine
Davidson
--------------After Removing 3rd Node--------------
Anbu
Arul
Bharath
Catherine
Davidson

Reverse a Linked List
Input

1 -> 2 -> 3 -> 4 -> 5 -> NULL 

Output

5 -> 4 -> 3 -> 2 -> 1 -> NULL 

Idea1: Using bruteforce copy the list in to Array and traverse the array backward and create new node
Idea2:

1. Use 3 Variables. Prev, Curr, Temp and traverse through list items
2. Start with Curr in Head and Prev as null
3. Move forward by making Temp to Curr.next, Curr.next to Prev
4. Prev should be set to Curr and Curr should be set to Temp

Refer Adv DSA 3 Note 5 Page 9

Previous -> Current -> Temp

Node.java

package com.mugil.org;
class Node{
	String content;
	Node next;
	Node head;
    public Node(String content){
	 this.content = content;
	}	
}

SimpleLinkedList.java

package com.mugil.org;

public class SimpleLinkedList {
    Node head;

    public void printLinkedList() {
        Node current = head;
        while (current != null) {
            System.out.println(current.content);
            current = current.next;
        }
    }
}

ReverseLinkedList.java

public class ReverseLinkedList {
    public static void main(String[] args) {
        SimpleLinkedList simpleLinkedList = new SimpleLinkedList();

        simpleLinkedList.insertNodeAtEnd("Anbu");
        simpleLinkedList.insertNodeAtEnd("Arul");
        simpleLinkedList.insertNodeAtEnd("Arasu");
        simpleLinkedList.insertNodeAtEnd("Bharath");
        simpleLinkedList.insertNodeAtEnd("Catherine");
        simpleLinkedList.insertNodeAtEnd("Davidson");

        simpleLinkedList.printLinkedList();

        reverseLinkedList(simpleLinkedList);
    }

    public static void reverseLinkedList(SimpleLinkedList simpleLinkedList){
        Node temp = simpleLinkedList.head;
        Node curr = temp;
        Node prev = null;


        while(temp != null){
            temp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = temp;
        }

        simpleLinkedList.head = prev;

        System.out.println("-----------------------------------");
        simpleLinkedList.printLinkedList();
    }
}

Output

Anbu
Arul
Arasu
Bharath
Catherine
Davidson
-----------------------------------
Davidson
Catherine
Bharath
Arasu
Arul
Anbu