單連結清單之連結清單的倒序

單連結清單的倒序

•  借助結點法

今天我們要講的如何将連結清單進行倒序的操作,連結清單的倒序操作我們講比較普通的一種，那就是借助另一條連結清單或者另一個頭節點來進行倒序的操作。

 首先我們如圖其中LA是我們的一條有資料的連結清單，L是一條隻有一個頭節點的連結清單，在這裡我們的算法思想是将LA上的結點一個個取下來，然後一個個插入到L這條新的連結清單上。在插入的時候我們有幾點要特别注意的就是怎樣取下一個結點後保證下一個結點仍然存在，不會造成斷鍊。

public LinkList<T> reverse_order(LinkList<T> LA) {             //   倒序單連結清單方法
		LinkList<T> L = new LinkList<T> ();
		Node<T> pb = LA.head.next;
		Node<T> pa = L.head;
		while(pb!=null) {
			head.next = pb.next;
			pb.next = pa.next;
			pa.next = pb;
			pb = head.next;
		}
		return L;
	}
           

 在這裡我取下“1”這個結點的時候運用的是head.next = pb.next;這樣子用而不是使用pb = pb.next; 是為了不造成斷鍊，取下了結點後我們就跟插入操作一樣，将這個結點插入到新的鍊中，然後接下來我們要重置一下我們原來的連結清單，這裡就使用到了我們的  pb = head.next; 将連結清單重置一下然後不斷得進行循環，最終得出答案。

•  就地倒序法

  這個是倒序單連結清單的另一種方法，這個方法是直接在連結清單上做改動，直接對連結清單進行排序。

 上圖是我們的例子，在這個例子中我們引用兩個指針、一個頭指針來進行講解，三個指針的順序我們是不可以調換的。

public LinkList<T> reverse_order1(LinkList<T> L)   //  就地倒序連結清單
	{
		Node<T> p = L.head;
		Node<T> q = L.head.next;
		Node<T> r = q.next;
		while(r!=null)
		{
			q.next = r.next;
			r.next = p.next;      // 前一個結點往後一個結點相接的時候需要找尋到前前一個結點，通過前前一個結點來索引
			p.next = r;
			r = q.next;
		}
		return L;
	}
           

 在這個循環中我們的循環次數的進行了四次，每一次的周遊分别是1234，2134，3214，4321.

 在這個代碼主要控制的是q和r指針，這兩個指針在進行交換的移動的時候千萬要注意，連結清單在查找結點的時候一定是通過它的前一個結點來找到它的下一個結點，是以我們while循環中的第二段代碼我們是不可以改成r.next = q; 的隻能是r.next = p.next;因為隻有這樣我們才能夠找到它的後繼結點不然就會造成斷鍊。下面的代碼是錯誤的，所示範的是斷鍊的情況。

public LinkList<T> reverse_order1(LinkList<T> L)   //  就地倒序連結清單
	{
		Node<T> p = L.head;
		Node<T> q = L.head.next;
		Node<T> r = q.next;
		while(r!=null)
		{
			q.next = r.next;
			r.next = q;      // 前一個結點往後一個結點相接的時候需要找尋到前前一個結點，通過前前一個結點來索引
			p.next = r;
			r = q.next;
		}
		return L;
	}
           

很明顯這是錯誤的代碼而造成了斷鍊。

 相比之下可能我們的就地倒序法所耗費的空間複雜度為O(1)、時間複雜度為O(n)，當然我們用借助結點法的話當然耗費的空間複雜度也比較多。