如何在不创建新结点的情况下逆转一个已知链表

Question

如何在不创建新结点的情况下逆转一个已知链表？
只用写出逆转链表的函数。

Answer 1

供参考：

//就地逆置  -- 不带头结点的链表  -- 引用
void reverse(SingleLinkedList * & head)
{
    SingleLinkedList* p=NULL, * q=NULL;
    p = head->next;
    head->next = NULL;
    while (p)
    {
        q = p;
        p = p->next;
        q->next = head;
        head = q;
    }
}
//就地逆置  -- 带头结点的链表
void reverse(SingleLinkedList * head)
{
    SingleLinkedList* p=NULL, * q=NULL;
    p = head->next;
    head->next = NULL;
    while (p)
    {
        q = p;
        p = p->next;
        q->next = head->next;
        head->next = q;
    }
}