1. NC78.反转链表

1.1. 题目描述

输入一个链表，反转链表后，输出新链表的表头。 示例1

输入

{1,2,3}

返回值

{3,2,1}

1.2. 解法一：常规解法

public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        ListNode temp = null;
        while(curr != null){
            temp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = temp;
        }
        return prev;
    }
}

1.3. 解法二 ： 栈

解题思路：因为栈是先进后出的。实现原理就是把链表节点一个个入栈，当全部入栈完之后再一个个出栈，出栈的时候在把出栈的结点串成一个新的链表。原理如下

import java.util.*;
public class Solution {
    public ListNode ReverseList(ListNode head) {
     Deque<ListNode> deque = new LinkedList<>();
     while(head != null){
         deque.offer(head);
         head = head.next;
     } 
     if(deque.isEmpty()){
         return null;
     }  
     ListNode node = deque.pollLast();
     ListNode dummy = node;
     while(!deque.isEmpty()){
         ListNode temp = deque.pollLast();
         node.next = temp;
         node = node.next;
     }  
     node.next = null;
     return dummy;
    }
}