Java 单向链表翻转

链表翻转的思路有很多，再此做个记录。 思路一：最简单的思路就是先遍历链表，逐一将链表里的节点放入到栈里面；然后在遍历栈，将栈里的元素在逐一出栈形成新的链表。主要是利用了栈的后进先出的特点。

	public static ListNode reverseListNodeByStack(ListNode node) {
		
		Stack stack = new Stack();
		ListNode head = node;
		//链表入栈
		while(head!=null) {
			//当前要入栈的头部节点
			ListNode currentHead=head;
			//移动head指针，指向下一个节点
			head=head.next;
			//将当前头部节点的next设置为null，这样就单独将头部节点放入栈了，其子节点不会入栈
			currentHead.next=null;
			stack.push(currentHead);			
		}

		ListNode newHead = stack.pop();
		//新链表的next节点
		ListNode currentNextNode=newHead;
		//出栈构成新链表
		while(!stack.isEmpty()) {
			ListNode popNode = stack.pop();
			currentNextNode.next=popNode;
			currentNextNode=popNode;

		}
		return newHead;
	}

思路二： 遍历链表，然后修改head.next的指向。每一次遍历都需要不断移动head指针 ，然后将新的head的next指向已经遍历过得节点就可以了：

	 /**
	  * 链表翻转
	  * @param node
	  */
	 public ListNode reverseListNode(ListNode node) {
		 //新链表的头部节点，刚开始肯定是null
		 ListNode newHead = null;
		 ListNode head=node;
         while (head != null) {
             //当前需要处理的链表
             ListNode oldHead= head;     
             //移动head，head.next指的是链表中未处理的部分
             head = head.next;
             //让链表的第一个元素指向已经翻转的链表
             oldHead.next = newHead;
             //将oldHead作为newhead的头部
             newHead= oldHead;
             
         }
         //输出已完成翻转的链表
         return newHead;
	 }

ListNode的代码如下，为了调试方便，特地重写了toString方法，用来打印链表的所有值：

public class ListNode {
	int val;
	ListNode next;

	ListNode() {
	}

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

	ListNode(int val, ListNode next) {
		this.val = val;
		this.next = next;
	}
	
	public String toString() {
		String str=""+val;
		ListNode temp = next;
		while(temp!=null) {
			str+=temp.val;
			temp=temp.next;
		}
		return str;
	}
}