两道链表面试题：反转链表和两两交换链表元素

今天介绍两道面试时经常被问到的链表问题：
1. 翻转链表
2. 两两交换链表元素（假定有偶数个元素），只能操作指针
注：每个节点的结构如下所示：

struct Node{
    int val;
    struct Node *pNext;
    Node(int x):val(x), pNext(NULL){}
};

解：1 倒查法：
代码如下，其中为了记录下一个要被插入的元素，需要使用指针next记录之：

void ReverseList(struct Node *&head){
    if(head== NULL) return;
    struct Node *trav = head->pNext, *next;
    head->pNext = NULL;
    while(trav){
        next = trav->pNext;
        trav->pNext = head;
        head = trav;
        trav=next;
    }
}

插入前后对照图如下：


2. 代码如下，这次需要记录当前交换的两个元素的前一个元素，这里使用指针pre来实现：

void ReverseAdjTwo(struct Node *&head){
    if(head == NULL) return;
    struct Node *first = head;
    struct Node *second = first->pNext;
    // first two element
    first->pNext = second->pNext;
    second->pNext = first;
    head = second;
    struct Node *pre = first;
    first = first->pNext;
    while(first){
        second = first->pNext;
        pre->pNext = second;
        first->pNext = second->pNext;
        second->pNext = first;
        pre = first;
        first = first->pNext;
    }
}

每一轮处理前后对比如下图：

这里，由于头结点两个没有pre，需要特殊处理一下~~~