「java递归链表反转」反转链表 Java
本篇文章给大家谈谈java递归链表反转，以及反转链表 Java对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。
本文目录一览：
Java HashMap扩容的时候，为什么要把Entry链表反转
我觉得应该是效率问题，如何不做反转在重新计算hash值后将要获得当前链表的最后一个元素，然后对最后一个元素的next属性添加一个节点信息，但是如果反转的话就不用了。
例子：
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (EntryK,V e : table) {
while(null != e) {
EntryK,V next = e.next;
//重新计算hash值
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
//这个是反转的写法 start
e.next = newTable[i];
newTable[i] = e;
e = next;
// 反转end
//这个是不反转的写法 start
EntryK,V newEntry = newTable[i];
e.next = null;
if(newEntry != null){
while(true){
if(newEntry.next == null){
newEntry.next = e;
break;
}
newEntry = newEntry.next;
}
}else{
newTable[i] = e;
}
e = next;
//不反转 end
}
}
}
单链表指针反转的递归写法？
先反转后面的链表，从最后面的两个结点开始反转，依次向前，将后一个链表结点指向前一个结点，注意每次反转后要将原链表中前一个结点的指针域置空，表示将原链表中前一个结点指向后一个结点的指向关系断开。
如何链表反转
链表反转
单向链表的反转是一个经常被问到的一个面试题，也是一个非常基础的问题。比如一个链表是这样的： 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;
}
}
如何使用递归和非递归方式反转单向链表
以下是对使用递归和非递归方式反转单向链表的示例进行了详细的分析介绍，需要的朋友可以过来参考下 问题： 给一个单向链表，把它从头到尾反转过来。比如： a - b - c -d 反过来就是 d - c - b - a 。分析： 假设每一个node的结构是：复制代码 代码如下: class Node { char value;Node next;}因 为在对链表进行反转的时候，需要更新每一个node的“next”值，但是，在更新 next 的值前，我们需要保存 next 的值，否则我们无法继续。所以，我们需要两个指针分别指向前一个节点和后一个节点，每次做完当前节点“next”值更新后，把两个节点往下移，直到到达最 后节点。 代码如下：复制代码 代码如下: public Node reverse(Node current) { //initialization Node previousNode = null; Node nextNode = null; while (current != null) { //save the next node nextNode = current.next; //update the value of "next" current.next = previousNode; //shift the pointers previousNode = current; current = nextNode;}return previousNode; }上面代码使用的是非递归方式，这个问题也可以通过递归的方式解决。代码如下：复制代码 代码如下: public Node reverse(Node current){if (current == null || current.next == null) return current; Node nextNode = current.next; current.next = null; Node reverseRest = reverse(nextNode); nextNode.next = current; } 递归的方法其实是非常巧的，它利用递归走到链表的末端，然后再更新每一个node的next 值 (代码倒数第二句)。
关于java递归链表反转和反转链表 Java的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。