Dissecting a Y-shaped list

Problem statement:


Two singly linked lists join at a common node, making a Y shape. It is guaranteed that the common tail does not loop back. Find the junction node. Linear time, constant space.

It is an exercise for my students; nothing competitive.

This is what's provided:

-
list.h

#ifndef LIST_H
#define LIST_H

#include 

typedef struct node_s node_t;

size_t list_size(node_t * head, node_t ** tail);
node_t * list_tail(node_t * head);
node_t * list_reverse(node_t * head);
node_t * list_nth_node_unguarded(node_t * head, size_t n);
#ifdef EXERCISE_TEST
void list_link_node(node_t * from, node_t * to);
node_t * create_silly_list(size_t n);
#endif
#endif

-
list.c

```
#include "list.h"
#include

struct node_s {
node_t * next;
};

void list_link_node(node_t from, node_t to)
{
from->next = to;
}

size_t list_size(node_t * head, node_t ** tail)
{
node_t dummy = { .next = head };
head = &dummy;

size_t size = 0;

while (head->next) {
size++;
head = head->next;
}

if (tail) {
*tail = head;
}

return size;
}

node_t list_tail(node_t head)
{
node_t dummy = { .next = head };
head = &dummy;

while (head->next) {
head = head->next;
}

return head;
}

node_t list_reverse(node_t head)
{
node_t * prev = NULL;

while (head) {
node_t * next = head->next;
head->next = prev;
prev = head;
head = next;
}

return prev;
}

node_t list_nth_node_unguarded(node_t head, size_t n)
{
while (n--) {
head = head->next;
}
return head;
}

#ifdef EXERCISE_TEST
#include
#include
#include

node_t find_junction(node_t , node_t *);

node_t * create_silly_list(size_t n)
{
node_t head = calloc(n, sizeof(head));
for (size_t i = 1; i < n; ++i) {
head[i - 1].next = &head[i];
}
return head;
}

bool test_excersize(size_t size1, size_t size2, size_t junction_index)
{
node_t * he

Is it a good exercise, or the algebra jumps out like Jack off the box?

The algebra is fine. That size_t x1_minus_x2 = x1_plus_y - x2_plus_y line wouldn't be necessary (IMHO even reduces readability), but apart from that it's reasonable.

However, your solution is worse than it needs to be. It merely stays in-place, while the optimal solution to this problem can treat the input as read-only and limit the working-set to constant space.

Your solution also depends on list_reverse being implemented as in-place and manipulating the original list. Depending on such behavior is IMHO pretty bad design. In fact, if I hadn't checked the source of list_reverse, I would have expected it to return a reversed copy instead. Which would obviously break your solution.

I would expect that your students will mostly just reverse both lists, traverse in lockstep and identify the last common node that way. Students have a tendency to trade algebra for brute force, if possible.

Smarter students will just read the length of both lists, skip the length difference, and then walk in lockstep until they find the common element. Which then also would fit better within the space complexity requirements, and requires no manipulation of the lists.

StackExchange Code Review Q#140831, answer score: 5