关于链表好像有一系列问题，这个是最简单的一个：

给定一个单链表，请将它倒转

很多时候，问题都是想起来容易做起来难，这个题目据说只有1/3的面试者能够正确写出来

本人刚写的，欢迎指点。

void inverseLinkList(List &head)
{
if (head == NULL || head->next == NULL)
{
    return;
}

List p = head->next;
List q = head;
head->next = NULL;

while(p)
{
    List t = p;
    p = p->next;
    t->next = q;
    q = t;
}
    head = q;
}

给出非递归和递归解法：

#include <iostream>

using namespace std;

struct Node
{
    int data;
    Node* next;
}*head;

// 非递归写法
Node* InverseLinkedList(Node* head)
{
    if(head == NULL)
        return NULL;
    Node* newHead = NULL;
    while(head != NULL)
    {
        Node* nextNode = head->next;
        head->next = newHead;
        newHead = head;
        head = nextNode;
    }
    return newHead;
}

// 递归写法
Node* InverseLinkedListRecur(Node* head)
{
    if(head == NULL)
        return NULL;
    if(head->next == NULL)
        return head;
    Node* newHead = InverseLinkedListRecur(head->next);
    Node *tmp = newHead;
    while(tmp->next != NULL)
    {
        tmp = tmp->next;
    }
    tmp->next = head;
    head->next = NULL;
    return newHead;
}

int main()
{
    // 构建链表 9->8->7->6->5->4->3->2->1->0->NULL
    for(int i = 0; i < 10; i++)
    {
        Node* node = new Node();
        node->data = i;
        node->next = head;
        head = node;
    }
    head = InverseLinkedList(head);
    Node *tmp = head;
    while(head != NULL)
    {
        cout << head->data << " ";
        head = head->next;
    }
    cout << endl;
    head = InverseLinkedListRecur(tmp);
    tmp = head;
    while(head != NULL)
    {
        cout << head->data << " ";
        head = head->next;
    }
    cout << endl;
    while(tmp != NULL)
    {
        Node* next = tmp->next;
        delete tmp;
        tmp = next;
    }
}

写一个Haskell版本的。

reverse :: [a] -> [a]  
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]

这个行么？

li = [1,2,3,4,5,6]

n = len(li)

for i in range(n):
    if(i == (n-1-i)):
        break
    a = li[i]
    li[i] = li[n-1-i]
    li[n-1-i] = a
    if((i+1) == (n-1-i)):
        break

贴个C语言的

#include <cstdio>
#include <cstdlib>

typedef struct Node
{
    int val;
    Node * next;
}Node;


void reverse(Node ** head)
{
    Node * cur = *head;
    Node * before = NULL;
    while(cur != NULL)
    {
        Node * q = cur -> next;
        cur -> next = before;
        before = cur;
        cur = q;
    }
    *head =  before;
}

int main()
{
    Node * head = NULL;
    for(int i = 0; i < 4; i++)
    {
        Node * temp =  (Node*)malloc(sizeof(Node));
        temp->val = i;
        temp->next = head;
        head = temp;
    }
    Node * p = head;
    while(p != NULL)
    {
        printf("%d\n",  p->val);
        p = p->next;
    }
    reverse(&head);
    while(head != NULL)
    {
        printf("%d\n",  head->val);
        head = head->next;
    }
    //free
}

写个大概c版本吧, pf, temp为临时指针，front，rear分别为链表头和尾指针，代码内不再做声明
pf = front;
front = rear;
rear = pf;
while (pf != null)
{
    temp = pf->next->next;
    pf->next->next = pf;
    pf = temp;
}

这个应该是正确的了

struct popNode
{
    int data;
    struct popNode* next;
};

struct popQueue
{
    struct popNode* front;
    struct popNode* rear;
    int count;
};

void initPopQueue(struct popQueue* pq)
{
    pq->front = pq->rear = NULL;
    pq->count = 0;
    return;
}

void enPopQueue(struct popQueue* pq, int x)
{
    /* 得到一个由newP指针所指向的新结点 */
    struct popNode *newP;
    newP = malloc(sizeof(struct popNode));
    if(newP == NULL){
        printf("内存空间分配失败！ ");
        return;
    }
    /* 把x的值赋给新结点的值域，把新结点的指针域置空 */
    newP->data = x;
    newP->next = NULL;

    /* 若链队为空，则新结点即是队首结点又是队尾结点 */
    if(pq->rear == NULL){
        pq->front = pq->rear = newP;
    }else{    /* 若链队非空，则依次修改队尾结点的指针域和队尾指针，使之指向新的队尾结点 */
        pq->rear = pq->rear->next = newP;
    }
    pq->count++;
    return;
}

void printQueue(struct popQueue *pq)
{
    struct popNode *temp;
    temp = pq->front;
    while(temp != NULL)
    {
        printf("%d,", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

前面均为测试辅助方法，下面这个是倒装链表的方法

void reverseQueue(struct popQueue* pq)
{
    struct popNode *t, *t2, *t3;

    if(pq->rear == NULL)
    {
        return;
    }
    else
    {
        t = pq->front;
        t2 = pq->front->next;

        while (t2 != NULL)
        {
            t3 = t2->next;
            t2->next = t;
            t = t2;
            t2 = t3;
        }

        pq->front->next = NULL;
        pq->rear = pq->front;
        pq->front = t;

    }
}

测试代码

int main (int argc, char *argv[])
{
    struct popQueue pQueue;

    initPopQueue(&pQueue);

    int i = 0;
    for (i = 0; i < 10; i++)
    {
        enPopQueue(&pQueue, i);
    }
    printQueue(&pQueue);
    reverseQueue(&pQueue);
    printQueue(&pQueue);
    return 0;

}

还是得仔细想想才行啊，哈哈

很经典的题目，给个自己的解答：

Node* reverse(Node *head)
{
Node *p = NULL, *q = head, *r;

while (q)
{
    r = q->next;
    q->next = p;
    p = q;
    q = r;
}

return q;

}

python有个内置的：

li=[1,2,3]
li.reverse()