单链表反转

一. 先画一个单链表，这个单链表有4个元素。思路就是，每次把第二个元素提到最前面来。比如下面是第一次交换，我们先让头结点的next域指向结点a2，再让结点a1的next域指向结点a3，最后将结点a2的next域指向结点a1，就完成了第一次交换。

第一次交换

然后进行相同的交换将结点a3移动到结点a2的前面，然后再将结点a4移动到结点a3的前面就完成了反转。

 第二次交换

 第三次交换

思路1：

这里我们需要额外的两个工作指针来辅助交换。这个下面的步骤慢慢理解下，结合图片。注意结点之间的关系要先断再连。

步骤：

1. 定义当前结点 current，初始值为首元结点，current = L->next;
2. 定义当前结点的后继结点 pnext， pnext = current->next; 
3. 只要 pnext 存在，就执行以下循环：
   • 定义新节点 prev，它是 pnext的后继结点，prev = pnext->next;
   • 把pnext的后继指向current, pnext->next = current;
   • 此时，pnext 实际上已经到了 current 前一位成为新的current，所以这个时候 current 结点实际上成为新的 pnext，current = pnext;
   • 此时，新的 current 就是 pnext，current = pnext;
   • 而新的 pnext 就是 prev，pnext = prev;
4. 最后将头结点与 current 重新连上即可，L->next = current;

函数设计如下：

/* 单链表反转/逆序 */
LinkList ListReverse(LinkList L)
{
    LinkList current,pnext,prev;
    if(L == NULL || L->next == NULL)
        return L;
    current = L->next;  /* p1指向链表头节点的下一个节点 */
    pnext = current->next;
    current->next = NULL;
    while(pnext)
    {
        prev = pnext->next;
        pnext->next = current;
        current = pnext;
        pnext = prev;
    }
    //printf("current = %d,next = %d 
",current->data,current->next->data);
    L->next = current;  /* 将链表头节点指向p1 */
    return L;
}