实现一个链表的反转算法。
这是以前面试的时候碰到过的一个题目

C的？我的方法可能比较笨 新建一个链表，读一个写一个...

网上比较多的实现是用C，今天看到坛子里大家对算法题的热衷，就拿出来一起讨论一下用Java实现

最简单的链表了...只有add和delete方法
反转的做法是从第2个Node开始
把每个Node挪到链表的头,也就是root的位置

1. 
   
2. public class LinkedList {
   
3.         protected Node root=null;
   
4.         public void add(int value){
   
5.                 Node n=new Node(value);
   
6.                 if(root!=null){
   
7.                         Node last=root;
   
8.                         while(last.next!=null)
   
9.                                 last=last.next;
   
10.                         last.next=n;
    
11.                 }else{
    
12.                         root=n;
    
13.                 }
    
14.         }
    
15.         public void delete(int p){
    
16.                 if(root==null){
    
17.                         System.out.println("链表为空");
    
18.                         return;
    
19.                 }
    
20.                 Node n=root;
    
21.                 Node front=null;
    
22.                 if(p==0){
    
23.                         root=n.next;
    
24.                 }
    
25.                 while(p>0){
    
26.                         front=n;
    
27.                         n=n.next;
    
28.                         p--;
    
29.                         if(n==null){
    
30.                                 System.out.println("越界");
    
31.                                 return;
    
32.                         }
    
33.                 }
    
34.                 front.next=n.next;
    
35.         }
    
36.         public void show(){
    
37.                 if(root!=null){
    
38.                         Node n=root;
    
39.                         do{
    
40.                                 System.out.println(n.value);
    
41.                                 n=n.next;
    
42.                         }while(n!=null);
    
43.                 }
    
44.         }
    
45.         //从root的next那个Node开始,挪到链表的最前面,就是root上面去
    
46.         public void reverse(){
    
47.                 if(root.next!=null){                        //起码2个元素才反转
    
48.                         Node n=root.next;                        //当前Node
    
49.                         Node front=root;                        //记录当前Node的前一个Node
    
50.                         while(n!=null){
    
51.                                 front.next=n.next;                //前一个Node的next指向当前Node的next,等于删掉当前Node
    
52.                                 n.next=root;                        //把删掉的当前Node挪到最前面
    
53.                                 root=n;                                        //root指向当前Node
    
54.                                 n=front.next;                        //下一个Node
    
55.                         }
    
56.                 }
    
57.         }
    
58.         public static void main(String[] args){
    
59.                 LinkedList l=new LinkedList();
    
60.                 l.add(2);
    
61.                 l.add(1);
    
62.                 l.add(65);
    
63.                 l.add(43);
    
64.                 l.add(6);
    
65.                 l.reverse();
    
66.                 l.show();
    
67.         }
    
68. }
    
69. 
    
70. class Node{
    
71.         public Node(int value){
    
72.                 this.value=value;
    
73.         }
    
74.         protected int value=0;
    
75.         protected Node next=null;
    
76. }

复制代码

温少邦 发表于 2012-7-21 21:47
最简单的链表了...只有add和delete方法
反转的做法是从第2个Node开始
把每个Node挪到链表的头,也就是root的 ...

谢谢支持，运行了一下，没有错误，可以支持反转

这么个理解不知道对不对：
1.准备工作：使用LinkList创建一个集合（他底层不是由链表实现的吗？正好可以用），往里面添加一对元素
2.使用Collections类中的静态方法reverse()进行反转操作
这样实现对吗？如有不同意见欢迎交流

先说下单向链表的反转：
声明函数原型为：
void reverseLinkedList(item * header);

    这里，item为链表的元素类型，并假定其中包含了一个指向下一个元素的指针字段：
item * next;
和一些数据字段。

    函数参数header是一个指向item类型数据的指针，顾名思义，这个item类型的数据就是要反转的单向链表的头元素(注意，这里假定了这个单向链表是有头元素，而且头元素的数据类型与链表元素的类型是一致的)。

    下面再做一些假设：

    程序声明了一个全局变量或者预编译的常量即：
const int NULL = 0;
或者，
#define NULL 0

    因此可以用NULL来表示一个空指针。

    于是我们规定，header指向的链表的最后一个元素的next值为NULL。

    现在我们来实现函数：

1. void reverseLinkedList(item * header){
   
2. 
   
3.     item * newNext = NULL, curItem = header->next, oldNext = header->next->next;
   
4. 
   
5.     while (oldNext != NULL){
   
6. 
   
7.         curItem->next = newNext;
   
8. 
   
9.         newNext = curItem;
   
10. 
    
11.         curItem = oldNext;
    
12. 
    
13.         oldNext = oldNext->next;
    
14. 
    
15.     }
    
16. 
    
17.     header.next = curItem;
    
18. 
    
19. }
    
20. 
    

复制代码

以上算法中，通过三个指针curItem, newNext, oldNext分别指向当前操作的元素、当前操作的元素在新链表中的next(也就是curItem在原链表中的前一个元素)和当前操作元素的在原链表中的next，这样既保证了将当前操作的元素的next指向了它的前一元素，又保证了当前操作元素在原链表中的next所指向的元素地址不会丢失。

    算法中还要注意这三个指针初始值的设置、主循环方式和循环停止条件的选择，让函数体最精简，避免无谓的条件测试。另外记得在退出函数之前更新header->next指针的内容，使其指向更新后链表的首元素。

    当然，如果你把函数原型声明为：
void reverseLinkedList(item * first);

    即参数为链表的第一个元素，则相应把函数实现为以下即可：

1. void reverseLinkedList(item * first){
   
2. 
   
3.     item * newNext = NULL, curItem = first, oldNext = first->next;
   
4. 
   
5.     while (oldNext != NULL){
   
6. 
   
7.         curItem->next = newNext;
   
8. 
   
9.         newNext = curItem;
   
10. 
    
11.         curItem = oldNext;
    
12. 
    
13.         oldNext = oldNext->next;
    
14. 
    
15.     }
    
16. 
    
17.     first = curItem;
    
18. 
    
19. }
    
20. 
    

复制代码

对于双向链表的反转，问题就变得简单了，实际上就是交换item中next和previous指针的内容，如果有头元素，更新头元素next指针，指向原链表的最后一个元素。这里就不写出实现过程了。希望可以帮到你。