题解 | #反转链表#

public class Solution {
	//方法一:尾插法构建单链表
	//head参数就是头指针，指向第一个数据节点
	public ListNode ReverseList1(ListNode head) {
		if (head == null){//空链表
			return null;
		}
		if (head.next==null) {//只有一个数据节点
			return head;//反转后仍然是它自己
		}
		ListNode current = head;//current指针指向head
		ListNode tmp = null;//用来指向current的后一个节点
		ListNode pre = null;//用来指向current的前一个节点
		while (current != null) {
			tmp = current.next;
			current.next = pre;
			pre = current;
			current = tmp;
		}
		return pre;
	}
	
	//方法二:头插法构建单链表
	//遍历链表中的每一个节点，然后将每个节点都插在新的头节点(newHead)的后面
	//结束后，再将newHead.next返回【这里一定是返回newHead.next，因为返回的是新链表的第一个节点代表的单链表】
	public ListNode ReverseList2(ListNode head) {
		if (head == null){//空链表
			return null;
		}
		if (head.next==null) {//只有一个数据节点
			return head;//反转后仍然是它自己
		}
		
		ListNode current=head;
		ListNode temp = null;//temp指向current的后一个节点
		ListNode newHead=new ListNode(0);//新的头节点，用来辅助头插法的节点插入操作
		while (current!=null) {
			temp=current.next;
			//将当前节点current摘下来，插入到新的头节点的后面【头插法核心代码】
			current.next=newHead.next;
			newHead.next=current;
			
			//然后current和temp都后移一步
			current=temp;//current指向temp
		}
		return newHead.next;//这里一定是返回newHead.next，即返回新链表的第一个节点代表的单链表
	}
	
	//方法三：用栈的先进后出
	public ListNode ReverseList3(ListNode head) {
	
		Stack<ListNode> stack=new Stack<>();
		
		//遍历单链表，将节点挨个入栈
		ListNode temp=head;
		while (temp.next!=null) {
			stack.push(temp);
			temp=temp.next;//temp后移
		}
		stack.push(temp);
		//入栈结束

		ListNode newHead=new ListNode(0);//新链表的辅助头节点
		ListNode aid=newHead;//辅助指针
		//然后栈中的节点挨个出栈
		while(stack.size()>0){
			aid.next=stack.pop();//出栈节点挂在aid的后面
			aid=aid.next;//后移
		}
		return newHead.next;//返回newHead.next即可，不要返回newHead【因为不需要头节点，只需要返回第一个数据节点代表的单链表即可】
	}
}