LeetCode Problem: #151 — #160

151. Reverse Words in a String

Given an input string s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

Example 1:

Input: s = "the sky is blue"
Output: "blue is sky the"

Example 2:

Input: s = "  hello world  "
Output: "world hello"
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:

Input: s = "a good   example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

Constraints:

• 1 <= s.length <= 104
• s contains English letters (upper-case and lower-case), digits, and spaces ' '.
• There is at least one word in s.

Follow-up: If the string data type is mutable in your language, can you solve it in-place with O(1) extra space?

You can solve this problem in Dart by splitting the input string into words, reversing the order of the words, and then joining them back into a string. Here’s the Dart code for the solution:

String reverseWords(String s) {
  List<String> words = s.split(' ');

  // Remove empty strings from the list (due to multiple spaces)
  words.removeWhere((word) => word.isEmpty);

  // Reverse the order of the words
  words = words.reversed.toList();

  // Join the reversed words into a string with a single space
  return words.join(' ');
}

void main() {
  // Example 1
  String s1 = "the sky is blue";
  print(reverseWords(s1)); // Output: "blue is sky the"

  // Example 2
  String s2 = "  hello world  ";
  print(reverseWords(s2)); // Output: "world hello"

  // Example 3
  String s3 = "a good   example";
  print(reverseWords(s3)); // Output: "example good a"
}

This Dart code defines a reverseWords function that takes a string s as input, splits it into words, removes any empty strings, reverses the order of the words, and then joins them back into a string with a single space. The main function demonstrates the usage with the provided examples.

152. Maximum Product Subarray

Given an integer array nums, find a subarray that has the largest product, and return the product.

The test cases are generated so that the answer will fit in a 32-bit integer.

Example 1:

Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

Constraints:

• 1 <= nums.length <= 2 * 104
• -10 <= nums[i] <= 10
• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You can solve this problem in Dart by iterating through the array and keeping track of the current maximum and minimum product ending at each position. This approach considers both positive and negative numbers, as well as the possibility of starting a new subarray.

Here’s the Dart code for the solution:

int maxProduct(List<int> nums) {
  if (nums.isEmpty) {
    return 0;
  }

  int maxEndingHere = nums[0];
  int minEndingHere = nums[0];
  int maxProduct = nums[0];

  for (int i = 1; i < nums.length; i++) {
    int temp = maxEndingHere;
    maxEndingHere = [
      nums[i],
      nums[i] * maxEndingHere,
      nums[i] * minEndingHere,
    ].reduce((a, b) => a > b ? a : b);

    minEndingHere = [
      nums[i],
      nums[i] * temp,
      nums[i] * minEndingHere,
    ].reduce((a, b) => a < b ? a : b);

    maxProduct = maxProduct > maxEndingHere ? maxProduct : maxEndingHere;
  }

  return maxProduct;
}

void main() {
  // Example 1
  List<int> nums1 = [2, 3, -2, 4];
  print(maxProduct(nums1)); // Output: 6

  // Example 2
  List<int> nums2 = [-2, 0, -1];
  print(maxProduct(nums2)); // Output: 0
}

This Dart code defines a maxProduct function that takes an integer array nums as input and returns the maximum product of a subarray. The main function demonstrates the usage with the provided examples.

153. Find Minimum in Rotated Sorted Array

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

• [4,5,6,7,0,1,2] if it was rotated 4 times.
• [0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

Example 1:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2:

Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3:

Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times.

Constraints:

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• All the integers of nums are unique.
• nums is sorted and rotated between 1 and n times.

To find the minimum element in a rotated sorted array, you can use a binary search algorithm to achieve O(log n) time complexity. Here’s the Dart code for the solution:

int findMin(List<int> nums) {
  int left = 0;
  int right = nums.length - 1;

  while (left < right) {
    int mid = left + (right - left) ~/ 2;

    if (nums[mid] > nums[right]) {
      // The minimum element is in the right half.
      left = mid + 1;
    } else {
      // The minimum element is in the left half or at mid.
      right = mid;
    }
  }

  return nums[left];
}

void main() {
  // Example 1
  List<int> nums1 = [3, 4, 5, 1, 2];
  print(findMin(nums1)); // Output: 1

  // Example 2
  List<int> nums2 = [4, 5, 6, 7, 0, 1, 2];
  print(findMin(nums2)); // Output: 0

  // Example 3
  List<int> nums3 = [11, 13, 15, 17];
  print(findMin(nums3)); // Output: 11
}

This Dart code defines a findMin function that takes a rotated sorted array nums as input and returns the minimum element in O(log n) time. The main function demonstrates the usage with the provided examples.

154. Find Minimum in Rotated Sorted Array II

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,4,4,5,6,7] might become:

• [4,5,6,7,0,1,4] if it was rotated 4 times.
• [0,1,4,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums that may contain duplicates, return the minimum element of this array.

You must decrease the overall operation steps as much as possible.

Example 1:

Input: nums = [1,3,5]
Output: 1

Example 2:

Input: nums = [2,2,2,0,1]
Output: 0

Constraints:

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• nums is sorted and rotated between 1 and n times.

Follow up: This problem is similar to Find Minimum in Rotated Sorted Array, but nums may contain duplicates. Would this affect the runtime complexity? How and why?

To find the minimum element in a rotated sorted array with duplicates, we can modify the binary search approach. The key idea is to handle the case where nums[mid] is equal to nums[right] by decrementing right until nums[mid] becomes different from nums[right]. This way, we can safely discard the duplicate values.

Here’s the Dart code for the solution:

int findMin(List<int> nums) {
  int left = 0;
  int right = nums.length - 1;

  while (left < right) {
    int mid = left + (right - left) ~/ 2;

    if (nums[mid] > nums[right]) {
      // The minimum element is in the right half.
      left = mid + 1;
    } else if (nums[mid] < nums[right]) {
      // The minimum element is in the left half or at mid.
      right = mid;
    } else {
      // Handle the case where nums[mid] is equal to nums[right].
      right--;
    }
  }

  return nums[left];
}

void main() {
  // Example 1
  List<int> nums1 = [1, 3, 5];
  print(findMin(nums1)); // Output: 1

  // Example 2
  List<int> nums2 = [2, 2, 2, 0, 1];
  print(findMin(nums2)); // Output: 0
}

This Dart code defines a findMin function that takes a rotated sorted array nums (with duplicates) as input and returns the minimum element in O(log n) time. The main function demonstrates the usage with the provided examples. The modification to handle duplicates does not affect the overall time complexity of O(log n).

155. Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

• MinStack() initializes the stack object.
• void push(int val) pushes the element val onto the stack.
• void pop() removes the element on the top of the stack.
• int top() gets the top element of the stack.
• int getMin() retrieves the minimum element in the stack.

You must implement a solution with O(1) time complexity for each function.

Example 1:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]
Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

Constraints:

• -231 <= val <= 231 - 1
• Methods pop, top and getMin operations will always be called on non-empty stacks.
• At most 3 * 104 calls will be made to push, pop, top, and getMin.

To implement the MinStack class with O(1) time complexity for each function, we can use an auxiliary stack to keep track of the minimum element at each step. The idea is to store pairs of values in the stack, where the first element of the pair is the actual value, and the second element is the minimum value up to that point.

Here’s the Dart code for the MinStack:

class MinStack {
  List<List<int>> stack;

  MinStack() {
    stack = [];
  }

  void push(int val) {
    int minVal = stack.isEmpty ? val : stack.last[1];
    minVal = (val < minVal) ? val : minVal;
    stack.add([val, minVal]);
  }

  void pop() {
    if (stack.isNotEmpty) {
      stack.removeLast();
    }
  }

  int top() {
    if (stack.isNotEmpty) {
      return stack.last[0];
    }
    return -1; // or any appropriate value for an empty stack
  }

  int getMin() {
    if (stack.isNotEmpty) {
      return stack.last[1];
    }
    return -1; // or any appropriate value for an empty stack
  }
}

void main() {
  MinStack minStack = MinStack();
  minStack.push(-2);
  minStack.push(0);
  minStack.push(-3);
  print(minStack.getMin()); // Output: -3
  minStack.pop();
  print(minStack.top());    // Output: 0
  print(minStack.getMin()); // Output: -2
}

In this implementation, the push method updates the minimum value in constant time by comparing the current value with the minimum value at the top of the stack. The pop, top, and getMin methods all operate in O(1) time by accessing the last element of the stack.

156. Binary Tree Upside Down

Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.

Example:

Input: [1,2,3,4,5]

    1
   / \
  2   3
 / \
4   5
Output: return the root of the binary tree [4,5,2,#,#,3,1]
   4
  / \
 5   2
    / \
   3   1

Clarification:

Confused what [4,5,2,#,#,3,1] means? Read more below on how binary tree is serialized on OJ.

The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.

Here’s an example:

1
  / \
 2   3
    /
   4
    \
     5

The above binary tree is serialized as [1,2,3,#,#,4,#,#,5].

To flip a binary tree upside down, we can recursively traverse the tree and reverse the left and right pointers. Here’s the Dart code to achieve this:

class TreeNode {
  int val;
  TreeNode? left;
  TreeNode? right;

  TreeNode(this.val, [this.left, this.right]);
}

TreeNode upsideDownBinaryTree(TreeNode root) {
  if (root == null || root.left == null) {
    return root;
  }

  TreeNode newRoot = upsideDownBinaryTree(root.left!);
  root.left!.left = root.right;
  root.left!.right = root;
  root.left = null;
  root.right = null;

  return newRoot;
}

// Utility function to print the tree in level order for verification
void printLevelOrder(TreeNode root) {
  if (root == null) {
    return;
  }

  List<TreeNode?> queue = [root];
  while (queue.isNotEmpty) {
    TreeNode? current = queue.removeAt(0);
    print(current!.val);

    if (current.left != null) {
      queue.add(current.left);
    }

    if (current.right != null) {
      queue.add(current.right);
    }
  }
}

void main() {
  // Example usage:
  TreeNode root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3));
  print("Original tree:");
  printLevelOrder(root);

  TreeNode flippedRoot = upsideDownBinaryTree(root);

  print("\nFlipped tree:");
  printLevelOrder(flippedRoot);
}

In this example, the upsideDownBinaryTree function recursively flips the left subtree and then updates the left and right pointers accordingly to create the upside-down tree. The utility function printLevelOrder is used to print the tree in level order for verification.

157. Read N Characters Given Read4

Given a file and assume that you can only read the file using a given method read4, implement a method to read n characters.

Method read4:

The API read4 reads 4 consecutive characters from the file, then writes those characters into the buffer array buf.

The return value is the number of actual characters read.

Note that read4() has its own file pointer, much like FILE *fp in C.

Definition of read4:

Parameter:  char[] buf
    Returns:    int

Note: buf[] is destination not source, the results from read4 will be copied to buf[]

Below is a high level example of how read4 works:

File file("abcdefghijk"); // File is "abcdefghijk", initially file pointer (fp) points to 'a'
char[] buf = new char[4]; // Create buffer with enough space to store characters
read4(buf); // read4 returns 4. Now buf = "abcd", fp points to 'e'
read4(buf); // read4 returns 4. Now buf = "efgh", fp points to 'i'
read4(buf); // read4 returns 3. Now buf = "ijk", fp points to end of file

Method read:

By using the read4 method, implement the method read that reads n characters from the file and store it in the buffer array buf. Consider that you cannot manipulate the file directly.

The return value is the number of actual characters read.

Definition of read:

Parameters:	char[] buf, int n
    Returns:	int

Note: buf[] is destination not source, you will need to write the results to buf[]

Example 1:

Input: file = "abc", n = 4
Output: 3
Explanation: After calling your read method, buf should contain "abc". We read a total of 3 characters from the file, so return 3. Note that "abc" is the file's content, not buf. buf is the destination buffer that you will have to write the results to.

Example 2:

Input: file = "abcde", n = 5
Output: 5
Explanation: After calling your read method, buf should contain "abcde". We read a total of 5 characters from the file, so return 5.

Example 3:

Input: file = "abcdABCD1234", n = 12
Output: 12
Explanation: After calling your read method, buf should contain "abcdABCD1234". We read a total of 12 characters from the file, so return 12.

Example 4:

Input: file = "leetcode", n = 5
Output: 5
Explanation: After calling your read method, buf should contain "leetc". We read a total of 5 characters from the file, so return 5.

Note:

1. Consider that you cannot manipulate the file directly, the file is only accesible for read4 but not for read.
2. The read function will only be called once for each test case.
3. You may assume the destination buffer array, buf, is guaranteed to have enough space for storing n characters.

To implement the read method in Dart using the provided read4 method, you can create a class that represents the file and implement the read method within that class. Here's an example implementation:

class File {
  String content;
  int pointer;

  File(String content) {
    this.content = content;
    this.pointer = 0;
  }

  int read4(List<char> buf) {
    int bytesRead = 0;
    while (bytesRead < 4 && pointer < content.length) {
      buf[bytesRead++] = content[pointer++];
    }
    return bytesRead;
  }

  int read(List<char> buf, int n) {
    int totalRead = 0;
    List<char> tempBuf = List<char>.filled(4, '\0');

    while (totalRead < n) {
      int bytesRead = read4(tempBuf);

      for (int i = 0; i < bytesRead && totalRead < n; i++) {
        buf[totalRead++] = tempBuf[i];
      }

      if (bytesRead < 4) {
        // Reached the end of the file
        break;
      }
    }

    return totalRead;
  }
}

void main() {
  // Example usage
  File file = File("abcdefghijk");
  List<char> buf1 = List<char>.filled(4, '\0');
  print(file.read4(buf1)); // Output: 4, buf1 = "abcd"

  List<char> buf2 = List<char>.filled(4, '\0');
  print(file.read4(buf2)); // Output: 4, buf2 = "efgh"

  List<char> buf3 = List<char>.filled(4, '\0');
  print(file.read4(buf3)); // Output: 3, buf3 = "ijk"

  // Test the read method
  List<char> buf4 = List<char>.filled(4, '\0');
  print(file.read(buf4, 4)); // Output: 4, buf4 = "abcd"
}

This implementation maintains a file pointer within the File class and uses the read4 method to read characters into temporary buffers. The read method then copies the characters from the temporary buffer to the destination buffer until the desired number of characters (n) is read or the end of the file is reached.

158. Read N Characters Given Read4 II — Call multiple times

Given a file and assume that you can only read the file using a given method read4, implement a method read to read n characters. Your method read may be called multiple times.

Method read4:

The API read4 reads 4 consecutive characters from the file, then writes those characters into the buffer array buf.

The return value is the number of actual characters read.

Note that read4() has its own file pointer, much like FILE *fp in C.

Definition of read4:

Parameter:  char[] buf
    Returns:    int

Note: buf[] is destination not source, the results from read4 will be copied to buf[]

Below is a high level example of how read4 works:

File file("abcdefghijk"); // File is "abcdefghijk", initially file pointer (fp) points to 'a'
char[] buf = new char[4]; // Create buffer with enough space to store characters
read4(buf); // read4 returns 4. Now buf = "abcd", fp points to 'e'
read4(buf); // read4 returns 4. Now buf = "efgh", fp points to 'i'
read4(buf); // read4 returns 3. Now buf = "ijk", fp points to end of file

Method read:

By using the read4 method, implement the method read that reads n characters from the file and store it in the buffer array buf. Consider that you cannot manipulate the file directly.

The return value is the number of actual characters read.

Definition of read:

Parameters:	char[] buf, int n
    Returns:	int

Note: buf[] is destination not source, you will need to write the results to buf[]

Example 1:

File file("abc");
Solution sol;
// Assume buf is allocated and guaranteed to have enough space for storing all characters from the file.
sol.read(buf, 1); // After calling your read method, buf should contain "a". We read a total of 1 character from the file, so return 1.
sol.read(buf, 2); // Now buf should contain "bc". We read a total of 2 characters from the file, so return 2.
sol.read(buf, 1); // We have reached the end of file, no more characters can be read. So return 0.

Example 2:

File file("abc");
Solution sol;
sol.read(buf, 4); // After calling your read method, buf should contain "abc". We read a total of 3 characters from the file, so return 3.
sol.read(buf, 1); // We have reached the end of file, no more characters can be read. So return 0.

Note:

1. Consider that you cannot manipulate the file directly, the file is only accesible for read4 but not for read.
2. The read function may be called multiple times.
3. Please remember to RESET your class variables declared in Solution, as static/class variables are persisted across multiple test cases. Please see here for more details.
4. You may assume the destination buffer array, buf, is guaranteed to have enough space for storing n characters.
5. It is guaranteed that in a given test case the same buffer buf is called by read.

To implement the read method in Dart using the given read4 method, you can create a class called Solution and define the read method inside it. Here's an example implementation:

class Solution {
  List<char> buffer = List<char>(4);
  int bufferIndex = 0;
  int bufferCount = 0;

  int read4(List<char> buf) {
    // This is a placeholder for the actual read4 implementation.
    // You should implement the logic to read 4 characters from the file.
    // For the purpose of this example, we assume it reads characters from a predefined source.
    int bytesRead = 0;
    while (bytesRead < 4 && bufferIndex < bufferCount) {
      buf[bytesRead++] = buffer[bufferIndex++];
    }
    return bytesRead;
  }

  int read(List<char> buf, int n) {
    int totalBytesRead = 0;
    boolean eof = false;

    // Continue reading until n characters are read or end of file is reached.
    while (!eof && totalBytesRead < n) {
      // If the buffer is empty, read more characters using read4.
      if (bufferIndex == bufferCount) {
        bufferIndex = 0;
        bufferCount = read4(buffer);
        eof = bufferCount == 0; // Check if we have reached the end of the file.
      }

      // Copy characters from the buffer to the destination buf.
      while (totalBytesRead < n && bufferIndex < bufferCount) {
        buf[totalBytesRead++] = buffer[bufferIndex++];
      }
    }

    return totalBytesRead;
  }
}

void main() {
  Solution sol = Solution();
  List<char> buf = List<char>(4);

  print(sol.read(buf, 1)); // Output: 1, buf should contain "a"
  print(sol.read(buf, 2)); // Output: 2, buf should contain "bc"
  print(sol.read(buf, 1)); // Output: 0, end of file, buf is empty
}

Note that this is a simplified example, and you’ll need to replace the read4 method with the actual implementation that reads characters from a file. The example assumes a simple case where the file contains characters "abcdefghijk".

159. Longest Substring with At Most Two Distinct Characters

Given a string s , find the length of the longest substring t that contains at most 2 distinct characters.

Example 1:

Input: "eceba"
Output: 3
Explanation: t is "ece" which its length is 3.

Example 2:

Input: "ccaabbb"
Output: 5
Explanation: t is "aabbb" which its length is 5.

To solve this problem in Dart, you can use a sliding window approach. Here’s a possible implementation:

int lengthOfLongestSubstringTwoDistinct(String s) {
  if (s == null || s.isEmpty) {
    return 0;
  }

  int maxLength = 0;
  int left = 0;
  Map<String, int> charFrequency = {};

  for (int right = 0; right < s.length; right++) {
    String char = s[right];
    charFrequency[char] = charFrequency[char] != null ? charFrequency[char] + 1 : 1;

    // If the number of distinct characters exceeds 2, move the left pointer
    while (charFrequency.length > 2) {
      String leftChar = s[left];
      charFrequency[leftChar]--;
      if (charFrequency[leftChar] == 0) {
        charFrequency.remove(leftChar);
      }
      left++;
    }

    // Update the maximum length
    maxLength = maxLength > right - left + 1 ? maxLength : right - left + 1;
  }

  return maxLength;
}

void main() {
  print(lengthOfLongestSubstringTwoDistinct("eceba")); // Output: 3
  print(lengthOfLongestSubstringTwoDistinct("ccaabbb")); // Output: 5
}

In this Dart code, we use a sliding window represented by the left and right pointers. We also use a charFrequency map to keep track of the frequency of characters in the current window. If the number of distinct characters exceeds 2, we move the left pointer until the number of distinct characters becomes 2 again. During this process, we update the maximum length whenever a longer valid substring is found.

160. Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

begin to intersect at node c1.

Example 1:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8
Input Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,0,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.

Example 2:

Input: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Reference of the node with value = 2
Input Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [0,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

Example 3:

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: null
Input Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.

Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.

To find the intersection of two linked lists in Dart, you can use the following code:

class ListNode {
  int val;
  ListNode? next;

  ListNode(this.val, [this.next]);
}

ListNode? getIntersectionNode(ListNode? headA, ListNode? headB) {
  if (headA == null || headB == null) {
    return null;
  }

  // Get the lengths of the linked lists
  int lengthA = getLength(headA);
  int lengthB = getLength(headB);

  // Move the pointers to the same starting position
  while (lengthA > lengthB) {
    headA = headA!.next;
    lengthA--;
  }

  while (lengthB > lengthA) {
    headB = headB!.next;
    lengthB--;
  }

  // Move both pointers until they meet at the intersection node (or null if no intersection)
  while (headA != headB) {
    headA = headA!.next;
    headB = headB!.next;
  }

  return headA;
}

int getLength(ListNode? head) {
  int length = 0;
  while (head != null) {
    length++;
    head = head.next;
  }
  return length;
}

void main() {
  // Example 1
  ListNode commonNode = ListNode(8, ListNode(4, ListNode(5)));
  ListNode listA = ListNode(4, ListNode(1, commonNode));
  ListNode listB = ListNode(5, ListNode(0, ListNode(1, commonNode)));
  print(getIntersectionNode(listA, listB)?.val); // Output: 8

  // Example 2
  ListNode listA2 = ListNode(0, ListNode(9, ListNode(1, ListNode(2, ListNode(4)))));
  ListNode listB2 = ListNode(3, ListNode(2, ListNode(4, commonNode)));
  print(getIntersectionNode(listA2, listB2)?.val); // Output: 2

  // Example 3
  ListNode listA3 = ListNode(2, ListNode(6, ListNode(4)));
  ListNode listB3 = ListNode(1, ListNode(5));
  print(getIntersectionNode(listA3, listB3)); // Output: null
}

This code defines a ListNode class for the linked list nodes and a function getIntersectionNode that takes two linked lists as input and returns the reference to the node where they intersect, or null if they don't intersect. The function uses O(1) memory and runs in O(n) time.