LL 1 - Single Linked List

Construction of Linked List

Input:
n = 5
arr = [1,2,3,4,5]
Output:
1 2 3 4 5
Explanation: Linked list for the given array will be 1->2->3->4->5

Here, the head points to a dummy which doesn't store anything. Later, when we return the new head pointer, we simply use head.next and send it.

If we don't want to use dummy node, then we need to manually create the node using the first element of the array. After that, we iterate through the remaining elements, and creating nodes for each one.

    public static Node constructLL(int arr[]){
        Node head = new Node();

        Node temp = head;
        for(int num: arr){
            temp.next = new Node(num);
            temp = temp.next;
        }

        return head.next;
    }

Node class

public class Node {
    public int val;
    public Node next;

    public Node() {
    }

    public Node(int val) {
        this.val = val;
    }
}

Search in Linked List

    boolean searchKey(int n, Node head, int key) {
        Node temp = head;
        while(temp!=null){
            if(temp.data==key) return true;
            temp = temp.next;
        }
        return false;
    }

Length of Linked List

class Solution {
    public int getCount(Node head) {
        int length = 0;
        Node temp = head;
        while(temp!=null){
            length+=1;
            temp = temp.next;
        }
        return length;
    }
}

Deletion of Node

Delete the first Node

    static Node deleteFirst(Node head) {
        if(head==null) return null;
        return head.next;
    }

Delete the Last Node

Stop the iteration before the last 2nd node.

Conditions to stop on

• last node: temp.next!=null

• 2nd last node: temp.next.next!=null

class Solution {
    static Node deleteLast(Node head) {
        if(head==null || head.next==null) return null;

        Node temp = head;
        while(temp.next.next!=null){
            temp = temp.next;
        }
        temp.next = null;
        return head;
    }
}

Delete the kth Node

    static Node deleteNode(Node head, int index) {
        if(head==null) return null;
        if(index==1) return head.next;

        int i = 1;
        Node temp = head;

        while(i<(index-1) && temp!=null){
            temp = temp.next;
            i+=1;
        }

        if(temp!=null && temp.next!=null)
            temp.next = temp.next.next;

        return head;
    }

Insertion of Node

Insert at First

    public static Node insertFirst(Node head, int x) {
        Node newNode = new Node(x);
        if(head==null) return newNode;

        newNode.next = head;
        return newNode;
    }

Insert at Last

    static Node insertLast(Node head, int x) {
        Node newNode = new Node(x);

        if(head==null) return newNode;

        Node temp = head;
        while(temp.next!=null){
            temp = temp.next;
        }
        temp.next = newNode;

        return head;
    }

Insert at kth Node

    static Node insertAtIndex(Node head, int index, int x) {
        Node newNode = new Node(x);

        if(head==null) return newNode;
        if(index==1){
            newNode.next = head;
            return newNode;
        }

        Node temp = head;
        int i = 1;
        while(i<(index-1) && temp!=null){
            temp = temp.next;
            i+=1;
        }

        if(temp!=null){
            newNode.next = temp.next;
            temp.next = newNode;
        }
        return head;
    }