给定单链表尾节点，如何查找头节点？附JSON示例场景

Alright, let's walk through how to find the head node (A) when you've got an unsorted collection of singly linked list nodes and know the tail is D. Here's a straightforward, step-by-step approach:

Step 1: Build a Reverse Predecessor Map #

First, we need a way to look up which node points to any given node. Since each node's next field points to its successor, we can iterate through all nodes and build a map where the key is a node's ID, and the value is the ID of the node that has it as its next (i.e., the predecessor).

For example, in JavaScript:

const nodes = [
  { "id": "A", "next": "B" },
  { "id": "B", "next": "C" },
  { "id": "C", "next": "D" },
  { "id": "D", "next": null }
];

// Create a map: { successorId: predecessorId }
const reverseMap = {};
nodes.forEach(node => {
  if (node.next !== null) {
    reverseMap[node.next] = node.id;
  }
});
// Result: reverseMap = { "B": "A", "C": "B", "D": "C" }

In Python, it looks like this:

nodes = [
    {"id": "A", "next": "B"},
    {"id": "B", "next": "C"},
    {"id": "C", "next": "D"},
    {"id": "D", "next": None}
]

reverse_map = {}
for node in nodes:
    if node["next"] is not None:
        reverse_map[node["next"]] = node["id"]

Step 2: Backtrack from the Tail to the Head #

Now that we have our reverse map, start at the known tail node (D) and keep looking up its predecessor. The first node that has no predecessor (meaning it doesn't exist as a key in our reverse map) is the head node—since no other node points to it.

Here's how to implement this in JavaScript:

let currentId = "D";
let headId = null;

while (true) {
  const prevId = reverseMap[currentId];
  if (!prevId) {
    headId = currentId;
    break;
  }
  currentId = prevId;
}

console.log(headId); // Outputs: "A"

And in Python:

current = "D"
head = None

while True:
    prev = reverse_map.get(current)
    if not prev:
        head = current
        break
    current = prev

print(head)  # Outputs: "A"

Why This Works #

A singly linked list has exactly one head node (no other node's next points to it) and exactly one tail node (its next is null). By building our reverse map, we're essentially turning the list into a traversable structure in reverse. Starting from the tail, we follow the chain of predecessors until we hit the node with no predecessor—that's our head.

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