Two frequent questions on linked list in interviews

by e2718281828459045

Two questions from CC150:
2.6
Given a circular linked list, implement an algorithm which returns the node at the beginning of the loop.

shared_ptr<Linkedlist> cycle(shared_ptr<Linkedlist> head)
{
    shared_ptr<Linkedlist> slow = head, fast = slow;

    do {
        slow = forward(slow, 1);
        fast = forward(fast, 2);
    } while (slow != fast);

    slow = head;
    while (slow != fast) {
        slow = forward(slow, 1);
        fast = forward(fast, 1);
    }
    return fast;
}

shared_ptr<Linkedlist> last(shared_ptr<Linkedlist> head)
{
    while (head->next)
        head = head->next;

    return head;
}

shared_ptr<Linkedlist> forward(shared_ptr<Linkedlist> p, int k)
{
    while (k--)
        p = p->next;

    return p;
}

2.5 Implement a function to check if a linked list is a palindrome.

#include "Linkedlist.h"
#include <utility>

using namespace std;

pair<bool, shared_ptr<Linkedlist>> ispalindrome(shared_ptr<Linkedlist> head, int len)
{
    if (!len)
        return {true, head};
    else if (len == 1)
        return {true, head->next};

    auto result = ispalindrome(head->next, len - 2);
    auto last = result.second;

    if (!result.first || head->key != last->key)
        return {false, nullptr};
    else
        return {true, last->next};
}

int main()
{
    auto head = buildlist({});
    auto len = listlen(head);
    auto result = ispalindrome(head, len);
    cout << result.first << endl;
}