反转链表，链表带有头节点

reverseList.c

#include <stdio.h>
#include <stdlib.h>
struct Node;
typedef struct Node * ptrToNode;
typedef ptrToNode List,Position;

struct Node
{
    int element;
    ptrToNode  next;
};


List makeList()
{
    ptrToNode  head = (ptrToNode)malloc(sizeof(struct Node)),p = head;
    int n,e;
    head->next = NULL;
    printf("Please enter the number of elements in this list: ");
    scanf("%d",&n);
    for(int i = 0;i < n;i++)
    {
        printf("Enter the %dth element: ",i+1);
        scanf("%d",&e);
        ptrToNode  node = (ptrToNode)malloc(sizeof(struct Node));
        node->element = e;
        node->next = NULL;
        head->next = node;
        head = head->next;
    }
    return  p;
}

List reverse(List l)
{
    if (l == NULL && l->next == NULL)
        return  NULL;
    ptrToNode  head = l,next = NULL;
    ptrToNode  pre = NULL;
    ptrToNode  ptrToFirst = l->next;
    while (head != NULL)
    {
        next = head->next;
        head->next = pre;
        pre = head;
        head = next;
    }
    ptrToNode  newHead = (ptrToNode)malloc(sizeof(struct Node));
    newHead->next = pre;
    ptrToFirst->next = NULL;
    return newHead;
}

void printList(List l)
{
    Position  p = l->next;
    while (p != NULL)
    {
        printf("%d ",p->element);
        p = p->next;
    }
    printf("\n");
}


int main()
{
    List l = makeList();
    printList(l);
    List nl = reverse(l);
    printList(nl);
    return  0;
}

因为链表带有头节点，所以在反转后，需要再创建一个头节点，并将这个头节点的 next 指针指向原先的最后一个节点。