问题1

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
做法：利用栈的特性 实现首尾反转
要点： Stack s1 =new Stack()
head.next head.val
Stack.size()获取栈大小
示例 1：
输入：head = [1,3,2] 输出：[2,3,1]

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        Stack<Integer>  stack1 = new Stack<Integer>();
        while(head!=null){
            stack1.push(head.val);
            head=head.next;
        }
        int size =stack1.size();
        int[] a = new int[size];
       for(int i =0 ;i <size;i++){
           a[i]=stack1.pop();
       }
        return a;
    }
}
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

问题2：

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
这是一个改变指向问题 不等同于反转 没必要用栈来搞的复杂
用迭代做
原理
1->2->3->4->5->null
想要改变指向
利用一个中间结点 pre
一开始令pre为null next =head.next 是2
curr=head 是 1 令 curr.next=pre 完成1->null
pre =curr 变成 1
curr =next 完成当前 从1 变成2
curr.next=pre 完成 2->1 进行循环 终止条件是当curr =null时

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

问题3：

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;
    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    Map<Node, Node> cachedNode = new HashMap<Node, Node>();
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        if (!cachedNode.containsKey(head)) {
            Node headNew = new Node(head.val);
            cachedNode.put(head, headNew);
            headNew.next = copyRandomList(head.next);
            headNew.random = copyRandomList(head.random);
        }
        return cachedNode.get(head);
    }
}