链表反转--递归与非递归

package 链表上;

/**
 * 初始化链表节点
 * 
 * @author buder_cp
 *
 */
class ListNode {
	public int val;
	public ListNode next;

	public ListNode(int val) {
		super();
		this.val = val;
	}

	public ListNode(int val, ListNode next) {
		super();
		this.val = val;
		this.next = next;
	}
}

public class ReverseLinkedList {
	public static ListNode arrayToList(int[] array) {
		ListNode head = new ListNode(0);
		ListNode p = head;
		for (int value : array) {
			p.next = new ListNode(value);
			p = p.next;
		}
		return head.next;
	}

	public static void printList(ListNode head) {
		ListNode p = head;
		while (p != null) {
			System.out.print(p.val + " ");
			p = p.next;
		}
		System.out.println();
	}

	/**
	 * 链表反转，非递归
	 * 
	 * @param args
	 */
	public static ListNode reverseList(ListNode head) {
		ListNode pre = head;
		ListNode p  = head.next;
		ListNode next = null;
		while (p != null) {
			next = p.next;	//将next指向p.next
			p.next = pre;	//p.next指向前驱结点，开始逆转指针指向
			pre = p;	 	//pre指针后移
			p = next;		//p指针后移
		}
		head.next = null;
		return pre;
	}
	
	/**
	 * 链表反转，递归
	 * @param args
	 */
	public static ListNode reverseListRecursive(ListNode head) {
		//todo
		return null;
	}

	public static void main(String[] args) {
		int[] array = { 1, 2, 3, 4, 5, 6, 7 };
		ListNode head = arrayToList(array);
		System.out.print("normal list: ");
		printList(head);
		
		System.out.print("reverse: ");
		head = reverseList(head);
		printList(head);
	}
}