题目：有一个线性表（a1,a2,a3,....,an），采用带头节点的单链表L存储，设计一个算法将其就地逆置。所谓“就地”指辅助空间应该为O（1）。
方法一：采用头插法
先将L的头节点head的Next域置为NULL变成一个空链表，然后用p结点采用头插法插入到L中。
[java] view plaincopy
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即可。
[java] view plaincopy
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; } }
[java] view plaincopy
题目：有一个线性表（a1,a2,a3,....,an），采用带头节点的单链表L存储，设计一个算法将其就地逆置。所谓“就地”指辅助空间应该为O（1）。
方法一：采用头插法
先将L的头节点head的Next域置为NULL变成一个空链表，然后用p结点采用头插法插入到L中。
[java] view plaincopy
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即可。
[java] view plaincopy
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; } }
[java] view plaincopy