链表反转

题目很简单，一个单向链表，把尾指针指向前一个元素而不是后一个元素。如下

下面生成的是1，2，3，4，5，6。要求把它倒过来，尾部指向上一个节点，能够反向输出数据。

      typedef struct Node{
          int data;
          struct Node * next;
      }Node; //链表节点
       int a[] = {1,2,3,4,5,6};
        Node * item = (Node*)malloc(sizeof(Node));
        item->data = a[0];
        Node * head = item; //链表头部
        Node * p = item;//临时节点
        for (int i = 1; i<sizeof(a)/sizeof(int); i++) {
            Node * item = (Node*)malloc(sizeof(Node));
            item->data = a[i];
            p->next = item;
            p = p->next;
        }
        Node * start = head;
        while (start!= NULL) {
            printf("%d ",start->data);
            start = start->next;
        }

1. 利用栈的知识

思路很简单，实现起来也很简单，一次访问链表的每个节点，放入栈里面，然后将每个节点依次出栈，取出栈顶的元素放在已经出栈的元素的后面。这个感觉实现起来很简单，很容易想到。缺点就是需要分配额外空间，用两次循环。

2. 一次循环解决

每次都只看两个节点。只考虑把后面的节点的next指针指向前一个，然后两个节点同时向后移动一位，暂时不考虑第一个节点的next，把第一个节点单独处理，不然很难统一处理。

       start = head;  //head是已经构建的链表的头部
        Node * pre = start; //前一个节点
        Node * next = start->next;//后一个节点
        while (pre&&next) {
            p = next->next;//先取到后一个节点的下一个节点，否则无法找到位置进行移动
            next->next = pre;//后一个节点指针指向前一个
            pre = next;//前一个节点后移一位
            next = p;//后一个节点后移一位
        }
        start->next = NULL;//这个要赋值为NULL，否则会和原来的第二个节点形成一个环。
        while (pre) {
            printf("%d ",pre->data);
            pre = pre->next;
        }