LinkedList

40. Reverse a Linked List

1. Problem Description: Reverse a singly linked list. You can find the problem on LeetCode here: https://leetcode.com/problems/reverse-linked-list/

2. Optimized Java Code for Reversing a Linked List:

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
    }
}

public class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        
        return prev;
    }
}

1. Algorithm Explanation and Interview Process: To reverse a linked list, we can use the iterative approach known as the "sliding pointers" technique. The basic idea is to have three pointers: one pointing to the current node (curr), one pointing to the previous node (prev), and one pointing to the next node (nextTemp). We need to reverse the links between the nodes.

• Initialize prev to null and curr to the head of the linked list.

• While curr is not null:

  • Store the next node in nextTemp.

  • Set the next node of curr to prev (reversing the link).

  • Update prev and curr to move one step forward in the linked list.

• Finally, return prev as the new head of the reversed linked list.

During an interview, the interviewer may ask you to write code on a whiteboard or a code editor. Make sure to discuss the algorithm with them, explaining the need for three pointers and how the links are being reversed. This demonstrates your understanding of linked lists and your ability to solve the problem efficiently.

1. Similar Problems: The reversal of a linked list can be seen as a fundamental operation in linked list manipulation. It serves as a basis for solving more complex problems related to linked lists. Some problems that can utilize a similar algorithm include:

• Reverse Linked List II: https://leetcode.com/problems/reverse-linked-list-ii/

• Palindrome Linked List: https://leetcode.com/problems/palindrome-linked-list/

• Remove Nth Node From End of List: https://leetcode.com/problems/remove-nth-node-from-end-of-list/

1. Similar Problem Solutions:

a) Reverse Linked List II:

public ListNode reverseBetween(ListNode head, int m, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;

    ListNode prev = dummy;
    for (int i = 1; i < m; i++) {
        prev = prev.next;
    }

    ListNode curr = prev.next;
    for (int i = m; i < n; i++) {
        ListNode nextTemp = curr.next;
        curr.next = nextTemp.next;
        nextTemp.next = prev.next;
        prev.next = nextTemp;
    }

    return dummy.next;
}

b) Palindrome Linked List:

public boolean isPalindrome(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;

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

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

    slow = reverseList(slow);
    fast = head;

    while (slow != null) {
        if (slow.val != fast.val) {
            return false;
        }
        slow = slow.next;
        fast = fast.next;
    }

    return true;
}

c) Remove Nth Node From End of List:

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;

    ListNode slow = dummy;
    ListNode fast = dummy;

    for (int i = 1; i <= n + 1; i++) {
        fast = fast.next;
    }

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

    slow.next = slow.next.next;

    return dummy.next;
}

41. Detect Cycle in a Linked List

Sure! Here's the information you requested:

1. Problem Description and Link: Problem: Detect Cycle in a Linked List Link: https://leetcode.com/problems/linked-list-cycle/

2. Optimized Java Code with Detailed Comments:

// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast != null && fast.next != null) {
            slow = slow.next; // Move slow pointer by 1 step
            fast = fast.next.next; // Move fast pointer by 2 steps
            
            if (slow == fast) { // If slow and fast pointers meet, there is a cycle
                return true;
            }
        }
        
        return false; // If no cycle is found
    }
}

1. Algorithm Description and Interview Process: To detect a cycle in a linked list, we can use the Two Pointer Technique. We maintain two pointers - slow and fast. The slow pointer moves by 1 step at a time, while the fast pointer moves by 2 steps at a time. If the linked list has a cycle, the fast pointer will eventually catch up with the slow pointer. If there is no cycle, the fast pointer will reach the end of the list.

During an interview, it's important to properly understand and explain the algorithm. You can start by mentioning that the Two Pointer Technique is commonly used to solve linked list problems efficiently. Then, explain the steps involved in the algorithm and how it detects a cycle. Finally, discuss the time and space complexity of the algorithm.

1. Abstracted Problems: The algorithm to detect a cycle in a linked list can be applied to various other problems that involve finding loops or cycles in data structures. Some example problems include:

• Detect Cycle in a Directed Graph

• Find the Entry Point of a Linked List Cycle

• Find the Length of a Linked List Cycle

• Check if a Binary Tree has a Cycle

1. Similar Problems with Code and Descriptions: Here are a few similar problems with their corresponding optimized Java code and descriptions:

• Linked List Cycle II (https://leetcode.com/problems/linked-list-cycle-ii/) Description: Given a linked list, return the node where the cycle begins. If there is no cycle, return null. Code:

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        
        ListNode slow = head;
        ListNode fast = head;
        boolean hasCycle = false;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            
            if (slow == fast) {
                hasCycle = true;
                break;
            }
        }
        
        if (!hasCycle) {
            return null;
        }
        
        slow = head; // Move slow pointer to the head
        while (slow != fast) { // Move both pointers at the same speed until they meet
            slow = slow.next;
            fast = fast.next;
        }
        
        return slow; // Return the node where the cycle begins
    }
}

• Happy Number (https://leetcode.com/problems/happy-number/) Description: Given a positive integer, determine if it is a "happy" number. Code:

public class Solution {
    public boolean isHappy(int n) {
        int slow = n;
        int fast = n;
        
        do {
            slow = findSquareSum(slow);
            fast = findSquareSum(findSquareSum(fast));
        } while (slow != fast);
        
        return slow == 1;
    }
    
    private int findSquareSum(int n) {
        int sum = 0;
        while (n > 0) {
            int digit = n % 10;
            sum += digit * digit;
            n /= 10;
        }
        return sum;
    }
}

I hope this helps! If you have any further questions, feel free to ask.

42. Merge Two Sorted Lists

1. Problem:

Given two sorted linked lists, merge them into one sorted linked list and return the head of the merged list.

Problem link: https://leetcode.com/problems/merge-two-sorted-lists/

1. Optimized Java code for "Merge Two Sorted Lists":

// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode mergedHead = new ListNode(0);
        ListNode current = mergedHead;

        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }

        if (l1 != null) {
            current.next = l1;
        } else {
            current.next = l2;
        }

        return mergedHead.next;
    }
}

1. Detailed description of algorithm and thinking process during an interview:

The given problem can be solved using a simple iterative approach. We can maintain two pointers, one for each list, and compare the values at the corresponding positions.

Initially, we create a new merged list with a dummy node as the head. We then iterate through both lists, comparing the values. If the value of the node in the first list is smaller, we add it to the merged list and move the pointer of the first list forward. If the value of the node in the second list is smaller or equal, we add it to the merged list and move the pointer of the second list forward. We repeat this process until we reach the end of either list.

After this initial comparison, there will be at most one list that still has some remaining nodes. We simply append the remaining nodes of that list to the merged list.

Finally, we return the head of the merged list, which is the next node after the dummy head.

1. Problems where a similar algorithm can be used:

• Merge k Sorted Lists: This problem involves merging multiple sorted lists into a single sorted list. The same merge logic as in the "Merge Two Sorted Lists" problem can be applied here.

• Merge Intervals: This problem involves merging overlapping and adjacent intervals. The intervals can be considered as equivalent to the nodes in a linked list, and the merge logic can be applied accordingly.

1. Similar problems with detailed Java code and descriptions:

• Merge k Sorted Lists:

import java.util.Comparator;
import java.util.PriorityQueue;

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>(Comparator.comparingInt(node -> node.val));
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

        for (ListNode node : lists) {
            if (node != null) {
                minHeap.offer(node);
            }
        }

        while (!minHeap.isEmpty()) {
            ListNode node = minHeap.poll();
            current.next = node;
            current = current.next;
            if (node.next != null) {
                minHeap.offer(node.next);
            }
        }

        return dummy.next;
    }
}

• Merge Intervals:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

class Interval {
    int start;
    int end;

    Interval() {}

    Interval(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length <= 1) {
            return intervals;
        }

        Arrays.sort(intervals, Comparator.comparingInt(interval -> interval[0]));

        List<int[]> mergedIntervals = new ArrayList<>();
        int[] currentInterval = intervals[0];
        mergedIntervals.add(currentInterval);

        for (int[] interval : intervals) {
            if (interval[0] <= currentInterval[1]) {
                currentInterval[1] = Math.max(currentInterval[1], interval[1]);
            } else {
                currentInterval = interval;
                mergedIntervals.add(currentInterval);
            }
        }

        return mergedIntervals.toArray(new int[mergedIntervals.size()][]);
    }
}

These are some similar problems that can be solved using a similar merge logic as in the "Merge Two Sorted Lists" problem.

43. Merge K Sorted Lists

1. Problem Description: Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Problem link: https://leetcode.com/problems/merge-k-sorted-lists/

1. Java Code for "Merge K Sorted Lists":

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        
        return mergeHelper(lists, 0, lists.length - 1);
    }
    
    private ListNode mergeHelper(ListNode[] lists, int start, int end) {
        if (start == end) {
            return lists[start];
        }
        
        int mid = start + (end - start) / 2;
        ListNode left = mergeHelper(lists, start, mid);
        ListNode right = mergeHelper(lists, mid + 1, end);
        
        return mergeTwoLists(left, right);
    }
    
    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }
        
        if (l1 != null) {
            curr.next = l1;
        }
        
        if (l2 != null) {
            curr.next = l2;
        }
        
        return dummy.next;
    }
}

1. Algorithm Explanation:

The algorithm follows a divide and conquer approach. It recursively divides the lists into smaller sublists until there are only two lists left. Then, it merges these two lists using the mergeTwoLists() function, which is a typical merge sort algorithm for two sorted lists.

During an interview, you can explain the algorithm as follows:

• Identify that the problem can be solved using a divide and conquer approach to take advantage of the merge sort algorithm.

• Explain how the algorithm divides the list of k lists into two halves until there are only two lists left.

• Describe how the mergeTwoLists() function merges two sorted lists together.

1. Similar Problems Abstraction:

The algorithm used in "Merge K Sorted Lists" can be abstracted as a general merge sort algorithm for multiple lists.

1. Similar Problems with Java Code and Descriptions:

Problem 1: Merge Two Sorted Lists (https://leetcode.com/problems/merge-two-sorted-lists/)

Description: Given two sorted linked lists, merge them into a single sorted list. This problem is a simpler version of "Merge K Sorted Lists" and can be solved using the mergeTwoLists() function from the previous solution.

Java Code:

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }
        
        if (l1 != null) {
            curr.next = l1;
        }
        
        if (l2 != null) {
            curr.next = l2;
        }
        
        return dummy.next;
    }
}

Problem 2: Merge Sorted Array (https://leetcode.com/problems/merge-sorted-array/)

Description: Given two sorted arrays nums1 and nums2, merge them into nums1 as one sorted array. This problem is similar to "Merge Two Sorted Lists" and can be solved using a similar approach.

Java Code:

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;
        
        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }
        
        while (j >= 0) {
            nums1[k--] = nums2[j--];
        }
    }
}

These are just a few examples of similar problems that can be solved using a merge sort algorithm for multiple lists. There are many more variations and applications of this algorithm in different problem scenarios.

44. Remove Nth Node From End Of List

1. Problem Description and LeetCode Link:

The problem "Remove Nth Node From End Of List" requires us to remove the nth node from the end of a singly linked list and return the updated list.

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

1. Java Code:

Here's the optimized Java code for the problem "Remove Nth Node From End Of List" with detailed comments:

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0); // create a dummy node
        dummy.next = head; // dummy node points to the head
        ListNode slow = dummy; // initialize slow pointer to the dummy node
        ListNode fast = dummy; // initialize fast pointer to the dummy node

        // Move the fast pointer n+1 steps ahead
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }

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

        // Skip the nth node from the end by adjusting the pointers
        slow.next = slow.next.next;

        return dummy.next; // return the updated list
    }
}

1. Algorithm Explanation:

The algorithm uses the two-pointer approach to remove the nth node from the end of the list.

1. We introduce a dummy node to handle edge cases where the head needs to be removed.

2. We initialize both the slow and fast pointers to point to the dummy node.

3. We move the fast pointer n+1 steps ahead to create a gap of n nodes between the slow and fast pointers.

4. Then, we move both the slow and fast pointers together until the fast pointer reaches the end of the list.

5. When the fast pointer reaches the end, the slow pointer will be at the (n+1)th node from the end.

6. Lastly, we skip the nth node by adjusting the pointers and return the updated list.

During the interview process, it is important to communicate the steps and thought process clearly to the interviewer. Explain the use of the two-pointer technique and how it helps in finding the node to be removed without knowing the length of the list.

1. Abstraction:

The similar algorithm can be used in other problems that involve finding the nth node from the end or dealing with the concept of a sliding window with two pointers. Examples include finding the middle of a linked list, detecting a cycle in a linked list, and reversing a linked list in groups.

1. Similar Problems:

Here are some similar problems with detailed Java code and descriptions:

1. Middle of the Linked List: https://leetcode.com/problems/middle-of-the-linked-list/

public ListNode middleNode(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;

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

    return slow;
}

1. Detect Cycle in a Linked List: https://leetcode.com/problems/linked-list-cycle/

public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) {
        return false;
    }

    ListNode slow = head;
    ListNode fast = head;

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

        if (slow == fast) {
            return true;
        }
    }

    return false;
}

1. Reverse Linked List II: https://leetcode.com/problems/reverse-linked-list-ii/

public ListNode reverseBetween(ListNode head, int left, int right) {
    if (head == null || head.next == null || left == right) {
        return head;
    }

    ListNode dummy = new ListNode(0);
    dummy.next = head;

    ListNode prev = dummy;

    // Move prev to the node before the start of the sublist to be reversed
    for (int i = 1; i < left; i++) {
        prev = prev.next;
    }

    // Reverse the sublist
    ListNode curr = prev.next;
    for (int i = left; i < right; i++) {
        ListNode temp = curr.next;
        curr.next = temp.next;
        temp.next = prev.next;
        prev.next = temp;
    }

    return dummy.next;
}

These are just a few examples of similar problems that can be solved using the two-pointer approach. There are many more problems that can benefit from this technique.

45. Reorder List

1. Problem description and link: The problem "Reorder List" on LeetCode can be found here: https://leetcode.com/problems/reorder-list/

   Given a singly linked list L: L0→L1→...→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→...

2. Optimized Java code:

class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }

        // 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 prev = null;
        ListNode curr = slow.next;
        slow.next = null;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        
        // Merge the first half and the reversed second half of the linked list
        ListNode first = head;
        ListNode second = prev;
        while (second != null) {
            ListNode next1 = first.next;
            ListNode next2 = second.next;
            first.next = second;
            second.next = next1;
            first = next1;
            second = next2;
        }
    }
}

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

   • The problem asks us to reorder the list in a specific way, so we need to have a clear plan to solve it.

   • The first step is to find the middle of the linked list. We can use the slow and fast pointer technique here to find the middle node. This is a common technique to find the middle of a linked list.

   • After identifying the middle node, we need to reverse the second half of the linked list. To do this, we can use three pointers: prev, curr, and next. Repeatedly reverse the links between the nodes until we reach the end of the second half.

   • Once we have the reversed second half, we can start merging the first half (from the original head) and the reversed second half. We can use two pointers, first and second, to keep track of the nodes from the first half and the reversed second half respectively. During the merging process, we need to update the next pointers of the nodes properly.

   • Finally, we will have the reordered list as required.

2. Problems of similar algorithm: This algorithm can be used in problems where we need to reorder a linked list or manipulate a linked list in a specific way. Some examples include:

   • Reverse a linked list

   • Partition a linked list

   • Convert a linked list to binary search tree

   • Convert a sorted list to a balanced binary search tree

3. Similar problems with detailed Java code and descriptions:

   • Reverse a linked list:

   class Solution {
       public 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;
       }
   }

   • Partition a linked list:

   class Solution {
       public ListNode partition(ListNode head, int x) {
           ListNode beforeHead = new ListNode(0);
           ListNode before = beforeHead;
           ListNode afterHead = new ListNode(0);
           ListNode after = afterHead;
           while (head != null) {
               if (head.val < x) {
                   before.next = head;
                   before = before.next;
               } else {
                   after.next = head;
                   after = after.next;
               }
               head = head.next;
           }
           after.next = null; // Disconnect the end of the after list
           before.next = afterHead.next; // Connect the before list and the after list
           return beforeHead.next;
       }
   }

   • Convert a linked list to binary search tree:

   class Solution {
       public TreeNode sortedListToBST(ListNode head) {
           if (head == null) {
               return null;
           }
           ListNode mid = findMiddle(head);
           TreeNode root = new TreeNode(mid.val);
           if (head == mid) {
               return root;
           }
           root.left = sortedListToBST(head);
           root.right = sortedListToBST(mid.next);
           return root;
       }
       
       private ListNode findMiddle(ListNode head) {
           ListNode prev = null;
           ListNode slow = head;
           ListNode fast = head;
           while (fast != null && fast.next != null) {
               prev = slow;
               slow = slow.next;
               fast = fast.next.next;
           }
           if (prev != null) {
               prev.next = null; // Disconnect the left part
           }
           return slow;
       }
   }

   • Convert a sorted list to a balanced binary search tree:

   class Solution {
       public TreeNode sortedListToBST(ListNode head) {
           if (head == null) {
               return null;
           }
           return convert(head, null);
       }
       
       private TreeNode convert(ListNode head, ListNode tail) {
           if (head == tail) {
               return null;
           }
           ListNode mid = findMiddle(head, tail);
           TreeNode root = new TreeNode(mid.val);
           root.left = convert(head, mid);
           root.right = convert(mid.next, tail);
           return root;
       }
       
       private ListNode findMiddle(ListNode head, ListNode tail) {
           ListNode prev = null;
           ListNode slow = head;
           ListNode fast = head;
           while (fast != tail && fast.next != tail) {
               prev = slow;
               slow = slow.next;
               fast = fast.next.next;
           }
           if (prev != null) {
               prev.next = null; // Disconnect the left part
           }
           return slow;
       }
   }