反轉連結清單：空間複雜度為O(1)的算法

題目：反轉一個連結清單的資料，要求空間複雜度為O(1)

現在最怕的就是在規定的時間内用筆在紙上實作一個算法，第一眼看到這個題目的時候就想出了一個解決流程(因為是我第二次在紙上實作這個算法)，但是在紙上畫了流程之後，竟然把自己給繞暈了……

1、初始資料結構：

2、修改資料結構，添加頭結點

頭結點：link1.head 是用來記錄每次第一個節點被移除後新的第一個節點。

3、流程解釋

新增一個頭結點：link2.head

頭結點link2.head是用來記錄被翻轉連結清單的第一個節點的位置。

最終結果：

4、空間複雜度分析

在這個算法實作連結清單反轉過程中，隻添加了lin2.head、head1.head和臨時節點temp 3個節點，無論這個連結清單中元素數量如何，最終的占用的空間數量是固定的，是以空間複雜度是O(1)，時間複雜度為O(n)。

網上的解決辦法：http://blog.chenlb.com/2009/09/linked-list-reverse-time-space-complexity.html

代碼如下：

public class LinkedReverse {

Entity link1 = new Entity();//連結清單頭結點

Entity link2 = new Entity();//連結清單頭結點

/**

* 初始化連結清單

*/

public void init(){

for(int i = 0 ;i < 5 ;i++){

Entity e = new Entity(i,null);

Entity temp = link1;

while (temp.next != null) {

temp = temp.next;

}

temp.next = e;

}

}

/**

* 反轉連結清單

*/

public void reverse(){

Entity temp = null;

while (link1.next != null) {

temp = link2.next;//新連結清單的原第一個節點

link2.next = link1.next;//修改新連結清單的第一個節點指向

link1.next = link1.next.next;//修改原連結清單的第一個節點指向

link2.next.next = temp;//新連結清單第一個節點指向新連結清單原第一個節點

}

}

/**

* 輸對外連結表

* @param link

*/

public void echoEntiry(Entity link){

Entity temp = link;

while (temp.next != null) {

temp = temp.next;

System.out.print(temp);

}

System.out.println();

}

public static void main(String[] args) {

LinkedReverse r = new LinkedReverse();

r.init();

System.out.print("link1:");

r.echoEntiry(r.link1);

System.out.print("link2:");

r.echoEntiry(r.link2);

r.reverse();

System.out.print("link1:");

r.echoEntiry(r.link1);

System.out.print("link2:");

r.echoEntiry(r.link2);

}

/**

* 連結清單元素

* @author NathanLiu

* @date 2011-4-3

*/

class Entity{

private int value;

private Entity next = null;

public Entity(int value,Entity next){

this.value = value;

this.next = next;

}

public Entity() {

}

/*setter 和 getter方法*/

public String toString(){

return "[value="+value+"],";

}

}

}