lintcode 算法-- 35. 翻转链表

算法要求

35. 翻转链表
翻转一个链表

样例
样例1:
对于链表 1->2->3->null, 翻转链表为 3->2->1->null
样例2:
对于链表 1->2->3->4->null, 翻转链表为 4->3->2->1->null

算法思路

1.链表的翻转的实现，有两种实现方式：非递归 和 递归 的实现方式
2.非递归 的实现方式：

• 定义三个节点 first、sencode、reverseHead（临时节点）
  

3.递归 的实现：

• TODO 有待完善

算法实现

package com.lintcode.easy;

public class Reverse {
	// 非递归的方式实现的
	public static ListNode reverse(ListNode head) {
		if(head == null){
			return null;
		}

		ListNode first = head;
		ListNode reverseHead = null; 	//建立一个新的节点用来存放结果
		while (first != null) {
			// 头结点的下一个节点设置为null
 			ListNode second = first.next;
			first.next = reverseHead;
			reverseHead = first;
			first = second;
		}
		return reverseHead;
	}
	
	// 使用递归方式的方式实现的
	public static ListNode reverseList(ListNode head){
		if(head == null || head.next == null)
			return head;
		ListNode second = head.next;
		ListNode reverseHead = reverseList(second);
		second.next = head;
		
		head.next = null;
		return reverseHead;
	}

	public static void main(String[] args) {
		ListNode node1 = new ListNode(1);
		ListNode node2 = new ListNode(2);
		ListNode node3 = new ListNode(3);
		
		node1.next = node2;
		node2.next = node3;
		
		ListNode head = reverse(node1);
//		ListNode head = reverseList(node1);
		
		while(head!= null){
			if(head.next == null){
				System.out.print(head.val+"->null");
			} else {
				System.out.print(head.val+"->");
			}
			head = head.next;
		}
		
	}
}

/**  
 * 定义节点
 */
class ListNode {
	int val;
	ListNode next;

	public ListNode(int x) {
		this.val = x;
		this.next = null;
	}
}