如何实现无import的单链表按优先级移除并返回指定部分的函数

Got it, let's break down how to solve this problem without relying on any imports. We'll build everything from scratch, including the linked list node structure, then implement the core logic to extract nodes by priority while updating the original list.

1. Define the Singly Linked List Node #

Since we can't use imports, we'll create our own ListNode class to represent each node in the linked list. Each node will hold a value, a priority, and a pointer to the next node.

class ListNode:
    def __init__(self, value, priority=None, next_node=None):
        self.value = value
        self.priority = priority
        self.next = next_node
    
    def __repr__(self):
        # Helper method to print nodes in a readable format
        return f"ListNode(value={self.value}, priority={self.priority})"

2. Core Function: Remove and Return Nodes by Priority #

The function will traverse the original linked list, split nodes into two groups: those matching the target priority (to return) and those that stay in the original list. We'll use dummy nodes to simplify edge cases (like empty lists or target nodes at the start/end).

def remove_by_priority(head, target_priority):
    # Dummy nodes to handle edge cases without extra condition checks
    dummy_remaining = ListNode(None)
    current_remaining = dummy_remaining
    
    dummy_target = ListNode(None)
    current_target = dummy_target
    
    current = head
    while current:
        next_node = current.next  # Save next node before modifying links
        if current.priority == target_priority:
            # Add node to the target list
            current_target.next = current
            current.next = None  # Break link to original list
            current_target = current_target.next
        else:
            # Keep node in the original list
            current_remaining.next = current
            current_remaining = current_remaining.next
        current = next_node
    
    # Update the original list's head to the remaining nodes
    head = dummy_remaining.next
    # Return the extracted target list and updated original list
    return dummy_target.next, head

3. Example Usage #

Let's test the function with a sample linked list to see how it works:

# Build a sample linked list: 1(p1) -> 2(p2) -> 3(p1) -> 4(p3) -> None
node4 = ListNode(4, 3)
node3 = ListNode(3, 1, node4)
node2 = ListNode(2, 2, node3)
node1 = ListNode(1, 1, node2)

# Remove all nodes with priority=1
target_list, remaining_list = remove_by_priority(node1, 1)

# Print the extracted target list
print("Extracted Target List (priority=1):")
current = target_list
while current:
    print(current, end=" -> ")
    current = current.next
print("None")  # Output: ListNode(value=1, priority=1) -> ListNode(value=3, priority=1) -> None

# Print the modified original list
print("\nRemaining Original List:")
current = remaining_list
while current:
    print(current, end=" -> ")
    current = current.next
print("None")  # Output: ListNode(value=2, priority=2) -> ListNode(value=4, priority=3) -> None

4. Key Details to Note #

• No imports: Every part of the solution is self-contained, no external dependencies.
• Dummy nodes: These eliminate messy checks for empty heads or target nodes at the start/end of the list.
• Link management: We save the next node before modifying links to avoid losing the rest of the list, and break links for target nodes to ensure the returned sublist is independent.

内容的提问来源于stack exchange，提问作者KMAN