【AU】單連結清單就地逆置

單連結清單就地逆置

單連結清單的就地逆置是指輔助空間O(1)的逆置方法，有兩種方法：

第一種

普通循環（頭插法重建立立帶頭節點的新連結清單）

将頭結點摘下，然後從第一結點開始，依次前插入到頭結點的後面（頭插法），直到最後一個結點為止。

準備：工作結點被賦為第二個節點，第一個結點的後繼為空。

執行：工作結點的後繼為頭結點的後繼，頭結點的後繼為工作節點。一直循環周遊。

public void rePrintNode() {
		if(head==null||head.next==null||head.next.next==null) {
			return;
		}
		Node p=head.next.next;
		head.next.next=null;
		while(p!=null) {
			Node q=p.next;
			p.next=head.next;
			head.next=p;
			p=q;
		}
		printNode();
	}
           

第二種

遞歸

public Node rePrintNode2(Node head) {
		if(head==null||head.next==null||head.next.next==null) {
			return head;
		}
		Node newhead=rePrintNode2(head.next);
		head.next.next=head;
		head.next=null;
		return newhead;
	}