【算法题系列之三】单链表反转

问题：

实现单链表反转

答案：

链表准备

class Node {
	private int Data;// 数据域
	private Node Next;// 指针域
	public Node(int Data) {
		// super();
		this.Data = Data;
	}
	public int getData() {
		return Data;
	}
	public void setData(int Data) {
		this.Data = Data;
	}
 
	public Node getNext() {
		return Next;
	}
	public void setNext(Node Next) {
		this.Next = Next;
	}
}

public static void main(String[] args) {
		Node head = new Node(0);
		Node node1 = new Node(1);
		Node node2 = new Node(2);
		Node node3 = new Node(3);
		head.setNext(node1);
		node1.setNext(node2);
		node2.setNext(node3);
 
		// 打印反转前的链表
		Node h = head;
		while (null != h) {
			System.out.print(h.getData() + " ");
			h = h.getNext();
		}
		// 调用反转方法
		head = Reverse(head);
 
		System.out.println("\n**************************");
		// 打印反转后的结果
		while (null != head) {
			System.out.print(head.getData() + " ");
			head = head.getNext();
		}
	}

递归反转法：在反转当前节点之前先反转后续节点。这样从头结点开始，层层深入直到尾结点才开始反转指针域的指向。简单的说就是从尾结点开始，逆向反转各个结点的指针域指向

private static Node Reverse1(Node head) {
		if(head==null||head.getNext()==null){
			return head;
		}
		Node reHead = Reverse1(head.getNext());
		head.getNext().setNext(head);
		head.setNext(null);
		return reHead;
	}

遍历反转法：递归反转法是从后往前逆序反转指针域的指向，而遍历反转法是从前往后反转各个结点的指针域的指向

private static Node Reverse2(Node head) {
		if(head==null){
			return head;
		}
		Node pre = head;
		Node cur = head.getNext();
		Node temp;
		while (cur!=null) {
			temp = cur.getNext();
			cur.setNext(pre);
			pre = cur;
			cur=temp;
		}
		head.setNext(null);
		return pre;
	}