Tag Archives: Java

Find the Node Where Two Linked Lists Converge

Objective

Given the heads of two linked lists, find the node where they converge; if no such node is found, return null instead.

Observations

  1. To determine whether or not the two lists converge, we need to compare the nodes in the two lists.
  2. The first node in either list that also appears on the other list is the node where the lists converge.
  3. The two lists do not converge if they both contain distinct nodes.
Code
import java.util.*;

/**
*	Find the intersection point of two converging linked lists.
**/
class Solution {
	
	/**
	*	@param ListNode head The head of a linked list
	*	
	*	@return The number of nodes in the list 
	**/
	public static int getLength(ListNode head) {
		// List length
		int length = 0;
		// A pointer that walks through the list
		ListNode tmp = head;
		
		// If the current node exists
		while (tmp != null) {
			// Increment the counter
			length++;
			// Move forward to next node
			tmp = tmp.next;
		}
		
		// Return the length of the list
		return length;
	}
	
	public static ListNode getConvergentNode(ListNode headA, ListNode headB) {
		// Get the length of both lists
		int lengthA = getLength(headA);
		int lengthB = getLength(headB);
		
		// Create pointers to reference the heads of both lists
		ListNode tmpA = headA;
		ListNode tmpB = headB;
		
		// If list A is shorter, skip over the extra leading nodes in list B
		while (lengthA < lengthB) { 
			lengthB--; 
			tmpB = tmpB.next; 
		} // End once the lists at the end of both pointers are the same length 
		
		// If list B is shorter, skip over the extra leading nodes in list A 
		while (lengthA > lengthB) {
			lengthA--;
			tmpA = tmpA.next;
		} // End once the lists at the end of both pointers are the same length
		
		// Now that both list heads are pointing to the same number of nodes, 
		// walk the pointers forward until they match
		// We only need to check one node because the lists have the same length
		while (tmpA != null) {
			// If the two references point to the same node
			if (tmpA == tmpB) {
				// Return one of the references
				return tmpA;
			}
			
			// Walk pointers forward
			tmpA = tmpA.next;
			tmpB = tmpB.next;
		}
		
		// No intersection found
		return null;	
	}
	
	/**
	*	@param ListNode headA The head of the first list
	*	@param ListNode headB The head of the second list
	*
	*	@return A reference to the node where the two lists converged
	*			or null if they don't intersect
	**/
	public static ListNode getConvergentNodeSet(ListNode headA, ListNode headB) {
		// Pointers to the list heads
		ListNode tmpA = headA;
		ListNode tmpB = headB;
		
		// A set of all the nodes in one of the lists
		Set traversedNodes = new HashSet();
		
		// Use one pointer to iterate through the first list
		while (tmpA != null) {
			// Add each node to the set
			traversedNodes.add(tmpA);
			// Walk pointer forward
			tmpA = tmpA.next;
		}
		
		// Use the other pointer to iterate through the second list
		// to find the first already seen node
		while (tmpB != null) {
			// If current node was already seen when traversing listA
			if (traversedNodes.contains(tmpB)) {
				// The point of convergence was found, return the node
				return tmpB;
			}
			
			// Walk pointer forward
			tmpB = tmpB.next;
		}
		
		// No intersection found
		return null;
	}
}

class ListNode {
	/* The data value stored within the node */
	E data;
	/* A reference to the next element in the list */
	ListNode next;
	
	ListNode(E data) {
		this.data = data;
		this.next = null;
	}
}

Find Two Numbers That Sum to a Given Value

Objective

Given an array of integers and a value, find a pair of distinct elements in the array that sum to the given value.

Observations

  1. We want to find two elements satisfying:
    element1 + element2 = value
  2. We need to find element1 and element2 within the array that satisfy the equation above (if they even exist), but value is known.
  3. We can rearrange this equation as:
    • element1 = value - element2
    • element2 = value - element1
Code
import java.util.*;

class Solution {
		
	/**
	*	@param int[] nums An array of non-negative integers
	*	@param int sum The value the pair of elements must sum to
	*
	*	@return The distinct pair of VALUES in the array whose corresponding
	*			values sum to the value of 'sum', or [-1, -1] if not found.
	**/
    public static int[] twoSumValues(int[] nums, int sum) {
		// Create a map of num elements to indices
		Map numToIndex = new HashMap();
		
		// Fill the map
		for (int i = 0; i < nums.length; i++) {
			// It doesn't matter if indices are overwritten
			// because the final value will map to the largest index
			numToIndex.put(nums[i], i);
		}
		
		// Iterate through values from smallest index to largest
		// This ensures that overwritten values still match to later indices
		// (e.g., if sum is 4 and there is a 2 at both indices 0 and 1, map only contains 2 mapped to 1)
		for (int i = 0; i < nums.length - 1; i++) {
			
			// See if a match exists in map
			Integer index = numToIndex.get(sum - nums[i]);
			
			// If match exists and the second element's index is later than the first
			if (index != null && index > i) {
				// Return the pair of distinct indices
				return new int[]{nums[i], nums[index]};
			}
		}
		
		// No solution found
		return new int[]{-1, -1};
    }
	
	/**
	*	@param int[] nums An array of non-negative integers
	*	@param int sum The value 
	*
	*	@return The distinct pair of INDICES in the array whose corresponding
	*			values sum to the value of 'sum', or [-1, -1] if not found.
	**/
    public static int[] twoSumIndices(int[] nums, int sum) {
		// Create a map of num elements to indices
		Map numToIndex = new HashMap();
		
		// Fill the map
		for (int i = 0; i < nums.length; i++) {
			// It doesn't matter if indices are overwritten
			// because the final value will map to the largest index
			numToIndex.put(nums[i], i);
		}
		
		// Iterate through values from smallest index to largest
		// This ensures that overwritten values still match to later indices
		// (e.g., if sum is 4 and there is a 2 at both indices 0 and 1, map only contains 2 mapped to 1)
		for (int i = 0; i < nums.length - 1; i++) {
			
			// See if a match exists in map
			Integer index = numToIndex.get(sum - nums[i]);
			
			// If match exists and the second element's index is later than the first
			if (index != null && index > i) {
				// Return the pair of distinct indices
				return new int[]{i, index};
			}
		}
		
		// No solution found
		return new int[]{-1, -1};
    }
}

Permuting a String to Make a Palindrome

Objective

Given a string of characters, determine whether or not some permutation of the string creates a palindrome.

Observations

  1. A palindrome is a word that reads the same forward as it does backward.
  2. We can use a sequence of characters to build a palindrome if either of the following conditions are satisfied:
    • Each character occurs an even number of times.
    • Each character occurs an even number of times except for one character.
Code
import java.util.*;

class Solution {
	/**
	*	@param String s The string to check
	*	@return true if the string can be permuted into a palindrome
	**/
	public static boolean hasPalindromicPermutation(String s) {
		// Create a set to hold unmatched characters
		Set unmatched = new HashSet();
		
		for (int i = 0; i < s.length(); i++) {
			// The current character
			char c = s.charAt(i);
			
			// If the character exists in the set, remove it
			if (unmatched.contains(c)) {
				unmatched.remove(c);
			}
			// Character is unmatched, add it to the set
			else {
				unmatched.add(c);
			}
		}
		
		// For the string to be a palindrome, only 0 or 1 character can be unmatched
		return (unmatched.size() < 2);
	}
}