【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;
	}