九.反轉單向連結清單和雙向連結清單

【題目】

分别實作反轉單向連結清單和反轉雙向連結清單的函數

【要求】

如果連結清單長度為N，時間複雜度要求為O(N)，額外空間複雜度要求為O(1)

【分析思路及代碼實作】

反轉單向連結清單：

1.找到某一個節點的下一個結點

2.找到某一個結點的下一個位置

3.把後邊的節點都移動到他的前邊一位去

public static Node reverseList(Node head) {
		Node pre=null;
		Node next=null;
		while(head!=null) {
			//1.找到下一個結點(資料加上指針)
			next=head.next;
			//2.下一個結點的位置
			head.next=pre;
			//3.下一個結點位置上存放的是原來的前一個結點
			pre=head;
			//4.前一個結點位置上存放的是原來的後一個結點
			head=next;
		}
		return pre;
	}
           

反轉雙向連結清單：

1.找到某個結點的下一個結點資料

2.找到某個結點的上一個位置和後一個位置

3.把後邊的節點都移到他的前一位上去

//1.雙向連結清單的結構
public static class DoubleNode {
		public int value;
		public DoubleNode next;
		public DoubleNode last;
		public DoubleNode(int data) {
			this.value=data;
		}
	}

//2.反轉雙向連結清單的方法
	public static DoubleNode reverseList(DoubleNode head) {
		DoubleNode pre=null;
		DoubleNode next=null;
		while(head!=null) {
			//1.找到下一個結點用next表示（結點找到了）
			next=head.next;
			
			//2.找到後邊位置（要移動到前邊位置上去）
			head.next=pre;
			
			//3.找到前邊的位置（要移動到後邊位置上去）
			head.last=next;
			
			//4.head作為的是中間數，前邊位置上放的原來後邊的數就是head，head相當于中間位置，它放的是後邊的節點
			pre=head;
			head=next;
		}
		return pre;
	}