单链表的倒序

•  借助结点法

今天我们要讲的如何将链表进行倒序的操作,链表的倒序操作我们讲比较普通的一种，那就是借助另一条链表或者另一个头节点来进行倒序的操作。

 首先我们如图其中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)，当然我们用借助结点法的话当然耗费的空间复杂度也比较多。