用递归和非递归两种方法翻转一个链表

用递归和非递归两种方法翻转一个链表

先定义一下链表：

typedef struct node
{
ElemType data;
struct node * next;
}ListNode;
typedef struct
{
ListNode *head;
int size;
ListNode *tail;
}List;
/*********************************************************
非递归的翻转实际上就是使用循环，依次后移指针，
并将遇到的链表指针反转
*********************************************************/
void ReserveList(List * plist) //非递归实现，
{
ListNode * phead; //新链表的头开始的第一个节点
ListNode * pt; //旧链表的头开始的第二个节点
ListNode * pn; //旧链表头的下一个
phead = plist->head;
if(phead && phead->next&& phead->next->next) //首先确定
{
phead = plist->head->next; //新链表就是以第一个节点开始，依次在表头添加节点，添加的节点是旧链表的第一个节点
pt = phead->next; //旧链表，旧链表被取走头结点之后放入新链表的表头，
pn = pt->next;
phead->next = 0;
while(pt)
{
pn = pt->next; //pn是旧链表的第二个节点
pt ->next = phead; //取旧链表的第一个节点插入新链表
phead = pt;
pt = pn; //旧链表往后移动
}
}
plist->head->next = phead; //新链表重新赋值到整个链表
}
/*********************************************************
递归思想，原理也是从就链表上依次取元素放入到新链表
直到原始链表被取完，得到新链表
*********************************************************/
ListNode * ReserveListRe(ListNode * oldlist,ListNode * newlist)
{
ListNode * pt;
pt = oldlist->next; //取旧链表的表头，pt是现在的旧链表
oldlist->next = newlist; //就旧链表插入到新链表
newlist = oldlist; //如果旧链表是空，表示旧链表被取完了，新链表就是翻转之后的链表
return (pt == NULL) ? newlist : ReserveListRe(pt,newlist);
}

------------------------------------------------------------------------------------------------------------------------------------------------------

null 存储 struct 面试算法

用递归和非递归两种方法翻转一个链表

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

被问到的一个面试题，也是一个非常基础的问题。比如一个链表是这样的： 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则变成了链头，然后把它赋给头结点即可。

还有一种利用递归的方法。这种方法的基本思想是在反转当前节点之前先调用递归函数反转后续节点。源代码如下。不过这个方法有一个缺点，就是在反转后的最后一个结点会形成一个环，所以必须将函数的返回的节点的next域置为NULL。因为要改变head指针，所以我用了引用。算法的源代码如下：

linka* reverse(linka* p,linka*& head)
{
     if(p == NULL || p->next == NULL)
     {
          head=p;
          return p;
     }
     else
     {
          linka* tmp = reverse(p->next,head);
          tmp->next = p;
          return p;
     }
}

LinkNode *reverse_link_recursive(LinkNode *head){if(head == NULL)return NULL; LinkNode*curr , *reverse_head , *temp; if(head->next == NULL)   // 链表中只有一个节点，逆转后的头指针不变
        return head;else { curr= head; temp = head->next;    // temp为(a2,...an)的头指针
        reverse_head = reverse_link_recursive(temp);   // 逆转链表(a2,...an),并返回逆转后的头指针
        temp->next = curr;    // 将a1链接在a2之后
        curr->next = NULL; } return reverse_head;     // (a2,...an)逆转链表的头指针即为(a1,a2,...an)逆转链表的头指针
}

秒客网

用递归和非递归两种方法翻转一个链表

相关文章