單鏈表翻轉(zhuǎn)比如有如下鏈表：

      

需要按照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("鏈表翻轉(zhuǎn)1");
		N new1 = reverseOne(n);
		while (new1 != null) {
			System.out.println(new1.name);
			new1 = new1.nextN;
		}

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

		System.out.println("鏈表翻轉(zhuǎn)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; //前一個(gè)節(jié)點(diǎn)
			N curN = n.nextN; //當(dāng)前節(jié)點(diǎn)
			N nextN ;   //后一個(gè)節(jié)點(diǎn)
			while (null != curN) {
				nextN = curN.nextN;
				curN.nextN = preN;
				preN = curN;
				curN = nextN;
			}
			
			n.nextN = null;
			n = preN;
			
			return n;
			
		}
		return null;
	}

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

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

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

		// 在返現(xiàn)輸出節(jié)點(diǎn)
		n = null;
		for (N rn : nList) {
			if (n != null) {
				// 如果n不為空時(shí)
				rn.nextN = n;
			}
			n = rn;
		}

		return n;
	}

}

// 定義一個(gè)節(jié)點(diǎn)
class N {
	public String name;
	public N nextN;
}

轉(zhuǎn)自：http://blog.csdn.net/fengshizty/article/details/44460243

標(biāo)簽： seo

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請與原作者聯(lián)系。