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

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

点击(此处)折叠或打开

1. struct Node{
   
2.     int val;
   
3.     struct Node *pNext;
   
4.     Node(int x):val(x), pNext(NULL){}
   
5. };

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

点击(此处)折叠或打开

1. void ReverseList(struct Node *&head){
   
2.     if(head== NULL) return;
   
3.     struct Node *trav = head->pNext, *next;
   
4.     head->pNext = NULL;
   
5.     while(trav){
   
6.         next = trav->pNext;
   
7.         trav->pNext = head;
   
8.         head = trav;
   
9.         trav=next;
   
10.     }
    
11. }

插入前后对照图如下：


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

点击(此处)折叠或打开

1. void ReverseAdjTwo(struct Node *&head){
   
2.     if(head == NULL) return;
   
3.     struct Node *first = head;
   
4.     struct Node *second = first->pNext;
   
5.     // first two element
   
6.     first->pNext = second->pNext;
   
7.     second->pNext = first;
   
8.     head = second;
   
9.     struct Node *pre = first;
   
10.     first = first->pNext;
    
11.     while(first){
    
12.         second = first->pNext;
    
13.         pre->pNext = second;
    
14.         first->pNext = second->pNext;
    
15.         second->pNext = first;
    
16.         pre = first;
    
17.         first = first->pNext;
    
18.     }
    
19. }

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

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