本文主要是介绍笔试题--链表的反序算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
今天遇到一道笔试题,实现链表的反序,查了一些资料记录于此
例如:一个链表是这样的: 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;
}
还有一种利用递归的方法。这种方法的基本思想是在反转当前节点之前先调用递归函数反转后续节点。源代码如下。不过这个方法有一个缺点,就是在反转后的最后一个结点会形成一个环,所以必须将函数的返回的节点的next 域置为NULL。因为要改
这篇关于笔试题--链表的反序算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!