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 &lt;stddef.h&gt;

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 &lt;stdlib.h&gt;

struct node_s {
    node_t * next;
};

void list_link_node(node_t * from, node_t * to)
{
    from-&gt;next = to;
}

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

    size_t size = 0;

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

    if (tail) {
        *tail = head;
    }

    return size;
}

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

    while (head-&gt;next) {
        head = head-&gt;next;
    }

    return head;
}

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

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

    return prev;
}

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

#ifdef EXERCISE_TEST
#include &lt;stdlib.h&gt;
#include &lt;stdbool.h&gt;
#include &lt;stdio.h&gt;

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 &lt; n; ++i) {
        head[i - 1].next = &amp;head[i];
    }
    return head;
}

bool test_excersize(size_t size1, size_t size2, size_t junction_index)
{
    node_t * head1 = create_silly_list(size1);
    node_t * head2 = create_silly_list(size2);
    node_t * tail2 = list_tail(head2);
    node_t * real_junction = list_nth_node_unguarded(head1, junction_index);
    list_link_node(tail2, real_junction);
    node_t * junction = find_junction(head1, head2);
    free(head1);
    free(head2);
    return junction == real_junction;
}

int main()
{
    printf("%d\n", test(10, 20, 5));
    printf("%d\n", test(10, 20, 0));
    return 0;
}
#endif

Makefile

CFLAGS += --std=c99 -g -DEXERCISE_TEST

SRC := list.c main.c junction.c
OBJ := $(SRC:%.c=%.o)
DEP := $(SRC:%.c=%.d)

main: $(OBJ)
    $(CC) -o $@ $^

%.o: %.c
    $(CC) -c $(CFLAGS) -o $@ $&lt;

%.d: %.c
    $(CC) -c -MM -MT $(CFLAGS) -o $@ $&lt;

-include $(DEP)



This is what is expected:


junction.c

#include "list.h"
#include &lt;assert.h&gt;

node_t * find_junction(node_t * head1, node_t * head2)
{
    node_t * tail1;
    node_t * tail2;

    size_t x1_plus_y = list_size(head1, &amp;tail1);
    size_t x2_plus_y = list_size(head2, &amp;tail2);

    assert (tail1 == tail2);

    list_reverse(head1);
    size_t x1_plus_x2 = list_size(head2, 0);
    list_reverse(tail1);

    size_t x1_minus_x2 = x1_plus_y - x2_plus_y;
    size_t x1 = (x1_plus_x2 + x1_minus_x2) / 2;

    return list_nth_node_unguarded(head1, x1);
}



Students are fluent in c; in fact, a given part is mostly understood.

Questions:


Am I doing something wrong? I am mostly concerned with overflows in x1_minus_x2 = x1_plus_y - x2_plus_y.
Is it a good exercise, or the algebra jumps out like Jack off the box?
At the first glance, size_t list_size(node_t * head, node_t ** tail); violates the SRP. Really it does not, because tail computation comes free of cost. Is it obvious, or should I emphasize on it?
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.