参考答案
单向链表的反转是一个经常被问到的一个面试题,也是一个非常基础的问题。
比如一个链表是这样的: 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。因为要改变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; } }
以上,是Java面试题【单向链表的反转】的参考答案。
输出,是最好的学习方法。
欢迎在评论区留下你的问题、笔记或知识点补充~
—end—