實作單連結清單的就地逆置算法

題目：有一個線性表（a1,a2,a3,....,an），采用帶頭節點的單連結清單L存儲，設計一個算法将其就地逆置。所謂“就地”指輔助空間應該為O（1）。

方法一：采用頭插法

先将L的頭節點head的Next域置為NULL變成一個空連結清單，然後用p結點采用頭插法插入到L中。

static Node headInsert(Node head){
	  if(head == null || head.next == null){
	    System.out.println("逆置的單連結清單至少有2個結點");
	    return null;
	  }
	  else{
	    Node p = head.next;
	    head.next = null;
	    Node q = null;
	    while(p != null){
	      q = p;
	      p = p.next;
	      q.next = head;
	      head = q;
	    }
	    return q;
	  }
	}
           

方法二：

先将首節點的next置為NULL,用p,q指向單連結清單中相鄰的兩節點，将r指向q的下一個結點，然後同步後移。當q=NULL時，表示指向原單連結清單的尾結點，将L的next域指向p即可。

static Node invert(Node head){
	  Node p,q,r;
	  if(head == null || head.next == null){
	    System.out.println("逆置的單連結清單至少有2個結點");
	    return null;
	  }
	  else{
	    p = head;
	    q = p.next;
	    while(q != null){
	      r = q.next;
	      q.next = p;
	      p = q;
	      q = r;
	    }
	    head.next = null;
	    head = p;
	    return head;
	  }
	}