单链表翻转

一次遍历链表，原地改变链表。不占用额外资源。

原理：不断的将前后两个节点的前驱和后继关系改变方向。

最后将原头节点变为尾节点，尾节点变为头节点。

 

 

单向链表的反转是一个经常

被问到的一个面试题，也是一个非常基础的问题。比如一个链表是这样的： 1->2->3->4->5 通过反转后成为5->4->3->2->1。最容易想到的方法遍历一遍链表，利用一个辅助指针，存储遍历过程中当前指针指向的下一个元素，然后将当前节点元素的指针反转后，利用已经存储的指针往后面继续遍历。源代码如下：

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

void reverse(linka*& head)
{
     if(head ==NULL)
          return;
     linka*pre, *cur, *ne;
     pre=head;
     cur=head->next;
     while(cur)
     {
          ne = cur->next;// 保留后面节点信息
          cur->next = pre; // 改变前驱后继关系
          pre = cur;//  两个指针平移
          cur = ne;
     }
     head->next = NULL;
     head = pre;
}

 

解释：对于头结点后的下一个结点cur如果不为空，则得到它的下一个结点保存在ne结点中，然后把cur的下一个结点赋为cur的前一个结点pre，这样就实现了cur和它的前一个结点的交换，然后把cur结点赋给pre结点，把ne结点赋给cur，这就实现了cur结点和pre结点都向后移了一个结点，然后循环下去，一直到cur结点为空时，说明已到链表尾，这时把头结点的后一个结点指向空，说明头结点已经成了尾结点了，这个时候把pre结点已经是原链表的最尾端了，如果要实现翻转，则把它赋给头结点。

 

如上图所示，它是先翻转head和p1,使p1指向head,然后pre=cur;cur=ne;到第二次，继续翻转p1,p2,使p2指向p1,然后持续下去，一直到第四次，这时cur为空，而pre已到了原链表的最后一个结点，这时如果head的下一个结点为空，则说明head为链尾了，而pre则变成了链头，然后把它赋给头结点即可。

C#版本

//链表翻转

            public void Reverse()

            {

                 Node<int> p = head;

                Node<int> q = head.Next；

                Node<int> r = new Node<int>();

                while(q!= null)

                {

                    r = q.Next;

                    q.Next = p;

                    p=q;

                    q = r;

                }

                head.Next = null;

                head = p;

            }