LinkedList -- find nth element

    public Node findNthFromLast(int nth){

    

    Node firstPointer=first;

    Node secondPointer=first;

    

    for(int i=0;i<nth;i++){

    firstPointer=firstPointer.next;

    }

    while(firstPointer!=null){

    firstPointer=firstPointer.next;

    secondPointer=secondPointer.next;

    }

    

    return secondPointer;

    }

1) The basic concept of this program is to create 2 pointers , first and second.
2) Now, say we have to find nth element from the last.
3) Idea is to create a gap of n between first pointer and second pointer. That is some thing we do by moving the first pointer to nth position from starting.
4) Now iterate the first and second pointer together till first pointer becomes null.

Length of linkedList

    public int findLengthLinkedList(Node nd){

    

    int size=0;

    if(nd==null)

    return 0;

    

    while(nd!=null){

    nd = nd.next;

    size++;

    }

    

    return size;

    }

    

    public int findLengthLinkedListRecursion(Node nd){

    

    if(nd==null)

    return 0;

    

    int size = findLengthLinkedListRecursion(nd.next)+1;

    return size;

    }

Reverse Linked-list in Pairs (Iteration and recursions)

Reverse LinkedList in Pairs:-

Iterative Approach

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

public Node reverseTheLinkedListInPairs(Node nd){

Node current = nd;

Node temp=null;

Node head=null;

while(current!=null && current.next!=null){

if(temp!=null)

temp.next.next=current.next; //this step joins 2 to 3 when 3 & 4 exchange happens

temp = current.next;//This takes 2 in temp variable

current.next = temp.next; //this step joins 1 to 3

temp.next=current; //this step join 2 to 1

current=current.next; // this steps makes current as 3

if(head==null)

head=temp;// this is basically maintaining the root

}

return head;

}

Recursive Approach

    public Node reverseTheLinkedListInPairRecursion(Node nd){

    

    if(nd==null || nd.next==null)

    return nd;

    

    Node temp = nd.next;

    nd.next=temp.next;

    temp.next=nd;

    nd.next= reverseTheLinkedListInPairRecursion(nd.next);    

    return temp;

    }

LinkedList - Reverse (recursion and iterative)

Recursive Approach

//2->4->5->6->7->8

   public Node reverseTheLinkedlist(Node nd){    

  if(nd.nextNd==null)

  return nd;

   

  Node remaining = reverseTheLinkedlist(nd.nextNd);

  System.out.println("The value of remaining is : "+remaining.value);

       nd.nextNd.nextNd=nd;

       nd.nextNd=null;

  return remaining;

   }

1) In the above program, first we check if the node sent in the program argument is null or the next value to that node is null. If so, then we return the node sent in the function argument.

2) remaining -- The value of this node in this program will basically become the last node in the list. Here remaining will become 8.

3) In each return cycle of recursion (except the last node), node is swipped with its next value and the node is then set to null.

The program will work in the following way:-

remaining = 8

Cycle 1 : 8->7->null

remaining = 8

Cycle 2 : 7->6, so result will become 8->7->6

remaining = 8

Cycle 3 : 6->5, so result will become 8->7->6->5

likewise, it will work for node 2 & 4 also.

Iterative Approach

This is the iterative approach:-

public Node reverseTheLinkedList(Node nd){

Node current = nd;

Node previous=null;

Node next=null;

while(current!=null){

next=current.next;

current.next=previous;

            previous=current;

            current=next;

}

return previous;

}