coderz.py

Let us see a few problems based on Linked List.

Given a linked list of N nodes such that it may contain a loop.

A loop here means that the last node of the link list is connected to the node at position X(1-based index). If the link list does not have any loop, X=0.

Remove the loop from the linked list, if it is present, i.e. unlink the last node forming the loop.

Example:

Input:
N = 3
value[] = {1,3,4}
X = 2
Output: 1
Explanation: The link list looks like
1 -> 3 -> 4
     ^    |
     |____|    
A loop is present. If you remove it 
successfully, the answer will be 1.

Solution:

class Solution
{
    //Function to remove a loop in the linked list.
    public static void removeLoop(Node head){
        // code here
         Node slow = head, fast = head;
    
    // Detect loop using Floyd's algorithm
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            break;
        }
    }
    
    // If loop exists, find the start of the loop
    if (slow == fast) {
        slow = head;
        while (slow.next != fast.next) {
            slow = slow.next;
            fast = fast.next;
        }
        // Remove the loop by setting the next pointer of the last node in the loop to null
        fast.next = null;
    }
        
    }
}

Time Complexity: O(n)

Space Complexity: O(1)

The steps involved:

1. Detect the loop in the linked list using Floyd’s algorithm. When the slow and fast pointers meet, it means there is a loop in the linked list.
2. Once the loop is detected, initialize either the slow or the fast pointer to the head of the linked list.
3. Now, move both pointers one node at a time until they meet. The node where they meet is the start of the loop.
4. To remove the loop, set the next pointer of the node where the fast pointer met the slow pointer to null.

Given a linked list consisting of L nodes and given a number N. The task is to find the N^th node from the end of the linked list.

Example:

Input:
N = 2
LinkedList: 1->2->3->4->5->6->7->8->9
Output: 8
Explanation: In the first example, there
are 9 nodes in linked list and we need
to find 2nd node from end. 2nd node
from end is 8.  

Solution:

class Solution
{
    //Function to find the data of nth node from the end of a linked list.
    int getNthFromLast(Node head, int N)
    {
        Node slow = head;
    Node fast = head;

    // Move the fast pointer N nodes ahead of the slow pointer
    for (int i = 0; i < N; i++) {
        if (fast == null) {
            // The length of the linked list is less than N
            return -1;
        }
        fast = fast.next;
    }

    // Move both pointers together until the fast pointer reaches the end of the linked list
    while (fast != null) {
        slow = slow.next;
        fast = fast.next;
    }

    // At this point, the slow pointer will be pointing to the Nth node from the end of the linked list
    return slow.data;

     // Your code here 
    }
}

Time Complexity: O(n)

Space Complexity: O(1)

The two-pointer method can be used to find the Nth node from the end of a linked list.

• We keep two pointers on hand, one slow and one quick. Initially, both pointers point to the linked list’s head node.
• The fast pointer is moved N nodes ahead of the slow pointer.
• The points are then moved together until the fast pointer reaches the end of the linked list.
• The slow pointer will now point to the Nth node from the end of the linked list.
• If the linked list’s length is less than N, we return -1.

Given a singly linked list of size N of integers. The task is to check if the given linked list is palindrome or not.

Example:

Input:
N = 3
value[] = {1,2,1}
Output: 1
Explanation: The given linked list is
1 2 1 , which is a palindrome and
Hence, the output is 1.

Solution:

class Solution
{
    //Function to check whether the list is palindrome.
    boolean isPalindrome(Node head) 
    {
    Stack<Integer> stack = new Stack<Integer>();
    Node current = head;

    // Traverse the linked list and push all elements onto the stack
    while (current != null) {
        stack.push(current.data);
        current = current.next;
    }

    // Traverse the linked list again and compare with the popped element
    current = head;
    while (current != null) {
        if (current.data != stack.pop()) {
            return false;
        }
        current = current.next;
    }
    return true;
    }    
}

Time Complexity: O(n)

Space Complexity: O(n)

In this code, we used a stack to hold all the linked list elements. We traversed the linked list twice: first to push all the elements onto the stack and again to pop each element from the stack and compare it to the value of the current node. The linked list is a palindrome if all the components match.

Given a singly linked list of N nodes.
The task is to find the middle of the linked list. For example, if the linked list is
1-> 2->3->4->5,then the middle node of the list is 3.
If there are two middle nodes(in case, when N is even), print the second middle element.
For example, if the linked list given is 1->2->3->4->5->6, then the middle node of the list is 4.

Example:

Input:
LinkedList: 1->2->3->4->5
Output: 3 
Explanation: 
Middle of linked list is 3.

Solution:

class Solution
{
    int getMiddle(Node head)
    {
         Node slow = head;
        Node fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow.data;
    }
}

Time Complexity: O(n)

Space Complexity: O(1)

In this implementation, we use two pointers slow and fast to traverse the linked list. slow moves one node at a time, while fast moves two nodes at a time. When fast reaches the end of the list, slow will be pointing to the middle node. If the length of the list is even, then slow will be pointing to the second middle node.

We initialize both slow and fast to the head of the list, and then we iterate through the list as long as fast is not null and fast.next is not null. In each iteration, we move slow one step forward and fast two steps forward. When the loop terminates, slow will be pointing to the middle node.

Finally, we return the middle node.

Note: also read about DSA: Linked List

Follow Me

If you like my post please follow me to read my latest post on programming and technology.

https://www.instagram.com/coderz.py/

https://www.facebook.com/coderz.py