如何 循环单链表就地逆置 实验报告

Question

如题

Answer 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;
}

// 方法二：利用递归的方法。
//这种方法的基本思想是在反转当前节点之前先调用递归函数反转后续节点
//不过这个方法有一个缺点，就是在反转后的最后一个结点会形成一个环，
//所以必须将函数的返回的节点的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;
}
}