java手写链表逆序代码,java链表逆序输出

用java来编写一个单链表类的成员函数，实现对头结点的单链表就地逆置的操作

逆置有两种方法，第一是把所有节点反过来。还有一种就是改变节点中的值。

第一种情况，其实可以考虑用头插法，来实现逆置。

下面的算法是基于头插法的思想，逆置链表的，仅供参考。

LinkList anti_linklist(LinkList demo)

{

LInkList *p,*q;//work pointer

LinkList head;

head=new LinkList();

head-next=null;//init head pointer

p=demo-head-next;//make p points to the first node

if(p==null)

return null;//the linklist is null

while(p!=null)

{

q=p;

q-next=head-next;

head-next=q;

p=p-next;

}

}

相关问答

Q1: 关于java实现链表的问题，求高手解惑啊

我看了好长时间，终于明白你哪里错了。

1）先说一个你的程序不是算法问题的错误，你的链表的header里面不应该存放具体数据，也就是说header里面的data应该不用。虽然你的outputLink 方法把header里的data也输出了，但是reverse方法忽略了header里的数据，而且你不可能创建长度为0的链表，因为你的构造方法里面header不管n为多少，都会有数据。

2）reverse里的错误就是q与p在循环里是同一个对象，q.next就是p.next，循环第二行q.next=rev.header，因此p.next也是rev.header，所以最后一行p=p.next，p永远不会是null，死循环。

3）想说一个不是错误的问题，不要把java与c弄混，不要把c语言的用法套到java里，比如java里面是不建议在另一个类中直接调用其他类的数据域的，像你这里header.data，在Link类里调用Node的data数据域，这样会出问题，应该使用get与set方法。还有最好每个类都有构造方法，Node类也应该有一个。

个人意见，仅供参考，谢谢。

Q2: 写一个函数将一个链表逆序. 比如一个链表是这样的: 1->2->3->4->5 通过反转后成为5->4->3->2->1

//函数名 ：trav

//功能 ：链表逆序

//参数 ：链表头指针的指针

//返回值 ：成功返回1失败返回0

//说明 ：无

int trav(PNode *head){

PNode p_1,p_2,tmp;

//判断参数是否有效

if(*head == NULL)

return 0;

//判断是否少于两个节点

if((*head)-next == NULL)

return 1;

//处理多余两个节点的情况

p_1 = *head;

p_2 = (*head)-next;

tmp = (*head)-next-next;

do{

p_2-next = p_1;

p_1 = p_2;

p_2 = tmp;

} while (tmp((tmp=tmp-next)||1));

//逆序过后设置头指针

(*head)-next = NULL;

*head = p_1;

//逆序完成 返回

return 1;

}

写了一个 满足你要求不？

Q3: java:已知单链表H,利用栈的原理写一个算法将其倒置

import myjava.Node;

import myjava.SinglyLinkedList;

import myjava.SeqStack;

public class ReverseLinkedListE extends SinglyLinkedListE {

public ReverseLinkedList(){

super();

}

public void reverse(ReverseLinkedListE list){

SeqStackE stack = new SeqStackE();

NodeE p = this.head ;

while(p != null){

stack.push(p.data);

p = p.next;

}

list.clear();

while(!stack.isEmpty()){

list.add(stack.pop());

}

}

public static void main (String[] args) {

ReverseLinkedListInteger list = new ReverseLinkedListInteger();

for(int i = 1;i 6;i++){

list.add(0,new Integer(i));

}

System.out.println("单列表 "+list.toString());

list.reverse(list);

System.out.println("逆转后 "+list.toString());

}

}

Q4: 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);

}

Q5: 作为一个面试官，我会问初级java工程师哪些问题？

初级java工程师多数是刚毕业或者工作1,2年的新人。对于新人，面试中基础问题会问道很多，因为先要考察这个人的基础。

关于基础类的题目，我在面试初级java工程师的时候一般会问下面两大类问题，每类5个题目，这样下来我就基本可以了解这位工程师的程度了。

java基础类

面向对象基础类

java基础类

1.描述一下java的访问修饰符，和它们之间的区别？

回答：如果可以回到出public，private，protected，就算是ok；回答出default的，加分。

2. int和Integer 区别？

回答：如果回答出Integer是int的包装类，就算ok；回答出其他的基本类型和它们相应的包装类，加分。

3.如何定义一个单精度浮点类型的变量？

回答：float 变量名=1.2f ；回答出不加最后的f为双精度浮点类型，加分

4. equals和==的区别？

回答： equals是值比较（一般处理java开发都会这么说，算是ok的）而==是引用比较（或者对象比较）；回答equals是可以自定义的，加分

5.将一个数组作为参数传递到一个方法中，在方法中，数组内的元素值被改变了，那么在方法外部，这个数组内的元素是否也被改编了？

回答：是，因为java方法中传递的是引用，就ok。如果回答中，将引用说明了自己的理解，加分。

面向对象基础类

1.重载和重写的区别？

回答：这个看个人理解，理解没有什么大的偏差就ok；回答出多态相关的，加分。

2.构造方法能不能重载？

回答：可以重载，ok；回答构造方法时不能继承的，所以如果要调用指定父类构造器就必须重写子类构造方法，加分。

3.抽象方法（abstract）是否可以被final、static、native修饰？

回答：都不可以，因为抽象方法是必须子类实现的，final方法时不可以被重写的，static是父类必须实现的方法，native是本地语言实现的方法。回答出封装和继承相关的，加分

4.当父类引用指向子类对象的时候，子类重写了父类方法和属性，那么当访问属性的时候，访问是谁的属性？调用方法时，调用的是谁的方法？

回答：访问的是父类的属性，调用的是子类的方法，ok；如果可以画图解释的话，加分

5.抽象类和接口有什么异同？

回答：一些类定义上的区别，ok；回答在应用过程中，如何根据业务定义接口，加很多分

最后，如果前面问题回答的不错，会补充两个编程习惯问题。

1.在你写过的代码中，你写过超过2层的循环吗，怎么实现的？

回答：没有，就算ok；如果回答有，听一下实现，如果原因说不出来，扣分。

2.在你写过的代码中，if语句最多嵌套了几层，最多有多少分支，怎么实现的？

回答：3层以下，就算ok；如果回答3层以上，听一下实现，如果原因说不出来，扣分。

4，5个分支，就算ok；如果回答5个分支以上，听一下实现，如果原因说不出来，扣分。

最后两个题其实比较陷阱，但是正是一个反向的思考才能了解面试者之前的工作状态。

如果面试者在平日里就有好的习惯，自然不用担心。