链表相关算法题、编程题、面试题

如何实现单链表逆转，输入为一个头节点，输出一个头节点。

ListNote *listReverse(ListNote *head)
{
    ListNote *p, *q, *r;
    p = head;
    q = p->next;
    if (q) r = q->next;
    else r = NULL;
    if (head || head->next)
    {
        while (r)
        {
            q->next = p;
            p = q;
            q = r;
            r = r->next;
        }
        q->next = p;
        head->next = NULL;
    }
    return q;
}

如何去除链表中重复的元素，不许使用额外空间？

ListNote *removeDupList(ListNote *head)
{
    //q: the current node, p: the running node, r: the previous node
    ListNote *p, *q, *r;
    q = head->next;
    r = head;
    bool flag;
    while (q)
    {
        p = head;
        flag = false;
        while (p != q)
        {
            if (p->data == q->data)
            {
                flag = true;
                break;
            }
            p = p->next;
        }
        if (flag)
        {
            free(r->next);
            r->next = q->next;
        }
        else
        {
            r = r->next;
        }
        q = q->next;
    }
}