Linked List

11. Remove Nth Node From End of List

1. Problem Description: The problem is to remove the nth node from the end of a singly linked list. We are given the head of the linked list and the value of n. We need to remove the nth node from the end of the list and return the updated head.

LeetCode Problem Link: https://leetcode.com/problems/remove-nth-node-from-end-of-list/

1. Optimized Java Code:

public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // Create a dummy node to handle edge cases
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        ListNode slow = dummy;
        ListNode fast = dummy;
        
        // Move the fast pointer n nodes ahead
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }
        
        // Move both the slow and fast pointers until the fast pointer reaches the end
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        
        // Remove the nth node by updating the pointers
        slow.next = slow.next.next;
        
        return dummy.next;
    }
}

1. Algorithm Explanation:

   • We create a dummy node and set it as the next node to the head of the linked list. This step helps us handle edge cases such as removing the first node or removing the only node in the list.

   • We initialize both the slow and fast pointers to the dummy node. The idea behind this is to maintain a fixed gap of n nodes between the slow and fast pointers.

   • We move the fast pointer n nodes ahead by traversing the linked list. This ensures that the gap between the slow and fast pointers is maintained.

   • Next, we move both the slow and fast pointers in tandem until the fast pointer reaches the end of the list. At this point, the slow pointer will be pointing to the (n-1)th node from the end of the list.

   • Finally, we update the pointers to remove the nth node from the end. We do this by setting the next pointer of the (n-1)th node to skip the nth node.

   • Finally, we return the updated head of the linked list.

When thinking through this problem during an interview, it's important to:

• Clarify any questions about the problem requirements and constraints.

• Discuss possible approaches and their time/space complexity.

• Explain the chosen approach and reason about its correctness and efficiency.

• Write clean and readable code with detailed comments.

• Test the solution with different test cases to ensure correctness and discuss any potential edge cases.

12. Intersection of Two Linked Lists

1. The problem: Given two singly linked lists, determine if the two lists intersect. Return the intersecting node. The intersection point is defined based on the reference, not the value. If the lists do not intersect, return null.

Problem link on LeetCode: https://leetcode.com/problems/intersection-of-two-linked-lists/

1. Optimized Java code for the "Intersection of Two Linked Lists" problem with detailed comments:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // Step 1: Find the lengths of both linked lists
        int lenA = getLength(headA);
        int lenB = getLength(headB);
        
        // Step 2: Calculate the difference in lengths between the two linked lists
        int diff = Math.abs(lenA - lenB);
        
        // Step 3: Move the pointer of the longer list ahead by the difference in lengths
        if (lenA > lenB) {
            while (diff > 0) {
                headA = headA.next;
                diff--;
            }
        } else {
            while (diff > 0) {
                headB = headB.next;
                diff--;
            }
        }
        
        // Step 4: Traverse both linked lists simultaneously until a common node is found or the end of the lists is reached
        while (headA != null && headB != null) {
            if (headA == headB) {
                return headA;
            }
            headA = headA.next;
            headB = headB.next;
        }
        
        // Step 5: If no intersection is found, return null
        return null;
    }
    
    // Helper method to calculate the length of a linked list
    private int getLength(ListNode head) {
        int count = 0;
        while (head != null) {
            count++;
            head = head.next;
        }
        return count;
    }
}

1. Detailed description of the algorithm and how to think through it during the interview process:

In order to find the intersection point of two linked lists, we can follow the below steps:

Step 1: Find the lengths of both linked lists (lenA and lenB) using a helper method. This step allows us to identify the difference in lengths between the two lists.

Step 2: Calculate the absolute difference, diff, in lengths between the two linked lists.

Step 3: Move the pointer of the longer linked list (headA or headB) ahead by the difference in lengths (diff). This ensures that both lists have the same number of nodes to traverse from the intersection point.

Step 4: Traverse both linked lists simultaneously until a common node is found or the end of the lists is reached. This is done by comparing the nodes at each position and moving the pointers forward.

Step 5: If no intersection is found, i.e., both pointers reach the end of the lists, return null.

This algorithm utilizes the fact that after aligning both pointers at the same relative position, any further movements made by both pointers will be equal in terms of number of steps until an intersection (if it exists) or the end of the lists. By the end, if the two lists intersect, the pointers will land on the same node.

During an interview, it's important to communicate the steps of the algorithm clearly, mention the time and space complexity of the solution, and test the solution with different test cases to ensure correctness. Explaining the thought process and reasoning behind the algorithm will also demonstrate problem-solving skills to the interviewer.

13. Linked List Cycle II

1. Problem Description: The problem "Linked List Cycle II" on LeetCode asks us to find the node where a cycle begins in a given linked list. Given a linked list, we need to determine if it contains a cycle and return the node where the cycle starts. If the linked list does not contain a cycle, we need to return null.

Problem Link: https://leetcode.com/problems/linked-list-cycle-ii/

1. Java Code Solution with Detailed Comments:

public class Solution {
    public ListNode detectCycle(ListNode head) {
        // Step 1: Check if the given linked list is empty or contains only one node
        if (head == null || head.next == null) return null;

        // Step 2: Initialize two pointers, slow and fast, both starting from the head node
        ListNode slow = head;
        ListNode fast = head;

        // Step 3: Move slow pointer by one step and fast pointer by two steps until they meet
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) break; // Cycle detected, exit the loop
        }

        // Step 4: Check if the linked list has a cycle
        if (fast == null || fast.next == null) return null; // No cycle present, return null

        // Step 5: Reset slow pointer to the head node and move both slow and fast pointers by one step
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }

        // Step 6: Return the node where the cycle starts
        return slow;
    }
}

1. Algorithm Description and Interview Process Approach: To solve the "Linked List Cycle II" problem during an interview, we can use the Floyd's Tortoise and Hare algorithm. This algorithm helps us to determine if a linked list contains a cycle and find the starting node of the cycle.

The algorithm works as follows:

1. Initialize two pointers, slow and fast, both starting from the head node of the linked list.

2. Move the slow pointer by one step and the fast pointer by two steps until they meet or reach the end of the linked list. If they meet, it means a cycle is present in the linked list.

3. Reset the slow pointer to the head node and move both the slow and fast pointers by one step until they meet again. The meeting point will be the starting node of the cycle.

During an interview, it is essential to explain the algorithm to the interviewer. You can break down the algorithm into the following steps:

• Check if the linked list is empty or contains only one node.

• Initialize slow and fast pointers.

• Move the pointers.

• Check if a cycle is present.

• Reset the slow pointer and move both pointers.

• Return the starting node of the cycle.

By following this step-by-step approach, and explaining it to the interviewer while writing code, you can demonstrate your thought process and problem-solving skills effectively. Remember to add detailed comments to your code for better clarity and understanding.

14. Palindrome Linked List

1. Problem Description: The problem is to determine whether a given singly linked list is a palindrome. A palindrome is a word, phrase, number, or other sequence of characters that reads the same forward and backward.

Problem Link: https://leetcode.com/problems/palindrome-linked-list/

1. Optimized Java Code with detailed comments:

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        
        // Find the middle of the linked list
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // Reverse the second half of the linked list
        ListNode secondHalf = reverseList(slow.next);
        
        // Compare the first half and the reversed second half of the linked list
        ListNode curr1 = head;
        ListNode curr2 = secondHalf;
        while (curr2 != null) {
            if (curr1.val != curr2.val) {
                return false;
            }
            curr1 = curr1.next;
            curr2 = curr2.next;
        }
        
        return true;
    }
    
    // Function to reverse a linked list
    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

1. Algorithm Explanation: To solve this problem, we can follow the following steps:

• Check for base cases. If the linked list is empty or has only one node, it is considered a palindrome.

• Use two pointers, slow and fast, to find the middle of the linked list. This can be done by incrementing slow by one and fast by two until fast reaches the end of the list.

• Reverse the second half of the linked list starting from the node after the slow pointer. This can be done by using a three-pointer technique.

• Compare the values of corresponding nodes in the first half and the reversed second half. If any pair of nodes have different values, the linked list is not a palindrome.

• Return true if all pairs of nodes have the same value, indicating that the linked list is a palindrome.

During an interview, it is important to discuss and explain the algorithm step by step, highlighting the basic logic behind each step. It is also important to mention the time complexity of the solution, which is O(n) where n is the number of nodes in the linked list.

15. Reverse Linked List II

1. Problem Description: The problem "Reverse Linked List II" on LeetCode asks us to reverse a linked list from position m to n. We are given the head of the linked list and two integers m and n. We need to reverse the linked list from the position m to n (inclusive) and return the modified linked list.

   LeetCode Problem Link: https://leetcode.com/problems/reverse-linked-list-ii/

2. Optimized Java Code for "Reverse Linked List II" with Detailed Comments:

public class ReverseLinkedListII {

    public ListNode reverseBetween(ListNode head, int m, int n) {
        // Edge case: If the list is empty or only contains one node, return head
        if (head == null || head.next == null) {
            return head;
        }
        
        // Create a dummy node and assign it as the new head
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        // Create two pointers, prev and curr, and position them accordingly
        ListNode prev = dummy;
        for (int i = 0; i < m - 1; i++) {
            prev = prev.next; // Move prev to the node before position m
        }
        ListNode curr = prev.next; // Move curr to the node at position m
        
        // Reverse the sublist from m to n
        for (int i = m; i < n; i++) {
            ListNode temp = curr.next;
            curr.next = temp.next;
            temp.next = prev.next;
            prev.next = temp;
        }
        
        // Return the modified linked list
        return dummy.next;
    }
}

1. Detailed Description on the Algorithm and Interview Process Approach:

• Step 1: Handle Edge Cases

  • First, we need to handle the edge case where the list is empty or only contains one node. In such cases, there is no need to reverse the list, so we can return the head itself.

• Step 2: Create a Dummy Node

  • We create a dummy node and assign it as the new head to handle the case where the list needs to be reversed from the beginning. This allows us to easily manipulate the pointers without worrying about edge cases.

• Step 3: Position Prev and Curr

  • We initialize two pointers, prev and curr, and position them accordingly. The prev pointer will be positioned at the node before position m, and the curr pointer will be positioned at the node at position m. We use a for loop to move the prev pointer to the desired position.

• Step 4: Reverse Sublist from m to n

  • We use another for loop to reverse the sublist from position m to n. In each iteration, we perform the following steps:

    • Move the temp pointer to the node next to curr.

    • Assign the next pointer of curr to the next pointer of temp, effectively skipping over temp.

    • Assign the next pointer of temp to the next pointer of prev, effectively inserting temp after prev.

    • Assign the next pointer of prev to temp, effectively connecting prev to temp.

• Step 5: Return Modified Linked List

  • Finally, we return the modified linked list by accessing the next pointer of the dummy node.

During an interview, it is important to communicate your thought process clearly. You can start by explaining the problem statement and asking clarifying questions, if any. Then, outline your approach and break it down into steps. While writing the code, add comments to explain your thought process and the purpose of each line of code. It is also helpful to test your code with different test cases to ensure its correctness.