Deduplicate a Linked List

Given a singly linked list, remove duplicate values in-place. Variant A (sorted list): delete repeated nodes so each value appears once using O(1) extra space. Variant B (unsorted list): delete duplicates while preserving the first occurrence; provide two solutions— (1) using a hash set and (2) without extra memory using the runner technique. Define your ListNode type, explain correctness, analyze time and space complexity for each approach, and include tests for edge cases (empty list, single node, all duplicates, no duplicates).

Part 1: Deduplicate a Sorted Singly Linked List

You are given a sorted singly linked list. Remove duplicate values in-place so that each value appears exactly once.

The linked list is provided as a Python list of values in non-decreasing order. Your function should internally define a ListNode type, build the linked list, remove duplicates by rewiring next pointers, and return the final linked list as a Python list.

Since the list is sorted, any duplicates will appear next to each other.

Constraints

• 0 <= len(values) <= 200000
• -10^9 <= values[i] <= 10^9
• values is sorted in non-decreasing order

Examples

Example 1

Input: []
Output: []

Explanation: Edge case: an empty list stays empty.

Example 2

Input: [5]
Output: [5]

Explanation: Edge case: a single node has no duplicates to remove.

Hints

1. In a sorted list, duplicate values are always adjacent.
2. Use one pointer that compares the current node with its next node; only move forward when the values differ.

Part 2: Deduplicate an Unsorted Singly Linked List While Preserving First Occurrences

You are given an unsorted singly linked list. Remove duplicate values while preserving the first occurrence of each value.

The linked list is represented as a Python list. Implement both approaches inside one function:

• If method == 'hash', use a hash set to remove duplicates in linear time on average.
• If method == 'runner', do not use extra memory for seen values; instead, use the runner technique to delete later duplicates.

Your function should internally define a ListNode type, build the linked list, perform the requested deduplication, and return the final linked list as a Python list.

Constraints

• 0 <= len(values) <= 5000
• -10^9 <= values[i] <= 10^9
• method is either 'hash' or 'runner'

Examples

Example 1

Input: ([], 'hash')
Output: []

Explanation: Edge case: an empty list stays empty.

Example 2

Input: ([9], 'runner')
Output: [9]

Explanation: Edge case: a single node has no duplicates.

Hints

1. To preserve first occurrences, keep the first time a value appears and remove only later nodes with the same value.
2. The runner technique fixes one node at a time and scans the rest of the list to delete matching values.