正文
java链表反转示例代码 java反转一个链表
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
如何链表反转
链表反转
单向链表java链表反转示例代码的反转是一个经常被问到的一个面试题，也是一个非常基础的问题。比如一个链表是这样的： 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指针，所以java链表反转示例代码我用了引用。算法的源代码如下：
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;
}
}
相关问答
Q1: java反转链表 大神给我添加个注释好么，我自己研究
public class Linktest {
//反转方法 ，传入一个链表
public static LinkNode reversal(LinkNode list){
//pre用来存放前一个链表节点
LinkNode pre =list;
//取出下一个链表节点 ,cru 用来存放当前链表节点
LinkNode cru = list.getNext();
//next用来存放下一个链表节点
LinkNode next;
//如果当前节点不为空(这里意思是 如果传进来的list 有下一个节点就继续执行)
while(null!=cru){
//取出当前节点的下一个节点
next = cru.getNext();
//把前一个节点赋予当前节点的下一个节点(这里产生实际改变)
cru.setNext(pre);
//把当前节点变量赋予前一个节点的变量
pre=cru;
//把下一个节点变量赋予当前
cru = next;
}
//循环体内会循环到方法传入的LinkNode 没有前一个节点为止
//因为几次交换的原因
//因为循环结束,所以把next赋空
list.setNext(null);
//因为循环的原因,前一个节点实际是第一个节点
list=pre;
//返回第一个节点
return list;
}
public static void main(String[] args) {
LinkNode head = new LinkNode(0);
LinkNode tmp = null;
LinkNode cur = null;
for (int i = 1; i 10; i++) {
tmp = new LinkNode(i);
if (1 == i) {
head.setNext(tmp);
} else {
cur.setNext(tmp);
}
cur = tmp;
}
LinkNode h = head;
while (null != h) {
System.out.print(h.getVal() + " ");
h = h.getNext();
}
head = reversal(head);
System.out.println("\n**************************");
//打印反转后的结果
while (null != head) {
System.out.print(head.getVal() + " ");
head = head.getNext();
}
}
}
Q2: java linked list里的元素顺序反过来
定义一个LinkedListInteger templist = new LinkedList();来存储list里面的值，通过迭代list，将值插入在templist的头上，那么templist就是list的反转了，最后将templist赋值给list就行了！
如下代码：
public void reverse() {
LinkedListInteger list = new LinkedList();
LinkedListInteger templist = new LinkedList();
int i = 0;
while (i 6) {
list.add(i);
i++;
}
IteratorInteger it = list.iterator();
int m;
while (it.hasNext() i = 0) {
m = it.next();
templist.addFirst(m);
i--;
}
list = templist;
System.out.println(list);
}
运行结果为：
5 4 3 2 1 0
从API中可以看到List等Collection的实现并没有同步化，如果在多线程应用程序中出现同时访问，而且出现修改操作的时候都要求外部操作同步化；调用Iterator操作获得的Iterator对象在多线程修改Set的时候也自动失效，并抛出java.util.ConcurrentModificationException。这种实现机制是fail-fast，对外部的修改并不能提供任何保证。
Iterator是工作在一个独立的线程中，并且拥有一个 mutex锁，就是说Iterator在工作的时候，是不允许被迭代的对象被改变的。
Iterator被创建的时候，建立了一个内存索引表（单链表），这个索引表指向原来的对象，当原来的对象数量改变的时候，这个索引表的内容没有同步改变，所以当索引指针往下移动的时候，便找不到要迭代的对象，于是产生错误。
List、Set等是动态的，可变对象数量的数据结构，但是Iterator则是单向不可变，只能顺序读取，不能逆序操作的数据结构，当 Iterator指向的原始数据发生变化时，Iterator自己就迷失了方向。
所以如果像下面这么写就会抛出异常java.util.ConcurrentModificationException
：
public void reverse() {
LinkedListInteger list = new LinkedList();
int i = 0;
while (i 6) {
list.add(i);
i++;
}
IteratorInteger it = list.iterator();
int m;
while (it.hasNext() i = 0) {
m = it.next();
list.add(m);
list.remove(0);
i--;
}
System.out.println(list);
}
java链表反转示例代码的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于java反转一个链表、java链表反转示例代码的信息别忘了在本站进行查找喔。
