实现单链表的就地逆置算法

题目：有一个线性表（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;
	  }
	}