Java實現單鏈表翻轉

單鏈表翻轉比如有如下鏈表：

需要按照C B A 輸出，我們可以有好幾種方法：

package org.andy.test;

import java.util.ArrayList;
import java.util.List;
/**

@author andy
@version：2015-2-4 上午9:41:12

*/

public class LinkedReverse {

/**
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub
    N n = new N();
    n.name = "A";

    N n1 = new N();
    n1.name = "B";

    N n2 = new N();
    n2.name = "C";

    N n3 = new N();
    n3.name = "D";

    n1.nextN = n2;
    n.nextN = n1;
    n2.nextN = n3;
    N old = n;
    while (old != null) {
        System.out.println(old.name);
        old = old.nextN;
    }

    System.out.println("鏈表翻轉1");
    N new1 = reverseOne(n);
    while (new1 != null) {
        System.out.println(new1.name);
        new1 = new1.nextN;
    }

    /*
    System.out.println("鏈表翻轉2");
    N new2 = reverseTwo(n, null);
    while (new2 != null) {
        System.out.println(new2.name);
        new2 = new2.nextN;
    }

    System.out.println("鏈表翻轉3");
    N new3 = reverseThree(n);
    while (new3 != null) {
        System.out.println(new3.name);
        new3 = new3.nextN;
    }

    */
}

//采用交換前后值
public static N reverseOne(N n) {
    if (n != null) {
        N preN = n; //前一個節點
        N curN = n.nextN; //當前節點
        N nextN ;   //后一個節點
        while (null != curN) {
            nextN = curN.nextN;
            curN.nextN = preN;
            preN = curN;
            curN = nextN;
        }

        n.nextN = null;
        n = preN;

        return n;

    }
    return null;
}

//采用遞歸實現
public static N reverseTwo(N n, N newN) {
    // 采用遞歸 返回 返回條件是最后一個幾點nextN為空
    if (n == null) {
        return newN;
    }

    N nextN = n.nextN;
    n.nextN = newN;
    return reverseTwo(nextN, n);
}

//最爛的實現方式
public static N reverseThree(N n) {
    if (n == null) {
        return null;
    }
    // 定義一個集合 ，放在集合里面在單個反向指回
    List<N> nList = new ArrayList<N>();
    N p = n;
    while (p != null) {
        N node = new N();// 當前節點
        node.name = p.name;
        nList.add(node);
        p = p.nextN;
    }

    // 在返現輸出節點
    n = null;
    for (N rn : nList) {
        if (n != null) {
            // 如果n不為空時
            rn.nextN = n;
        }
        n = rn;
    }

    return n;
}


}
// 定義一個節點
class N {
    public String name;
    public N nextN;
}
</pre> 轉自：http://blog.csdn.net/fengshizty/article/details/44460243