一、剑指offer 06. 从尾到头打印链表

要求：输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

注意这里的头结点head是包含值val的。

解法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<ListNode> stack = new Stack<>();
        while(head!=null){
            stack.push(head);
            head = head.next;
        }
        int[] arr = new int[stack.size()];
        // 注意这里的循环结束条件是arr.length,不能用stack.size()。
        // 因为随着pop的进行，stack的size是慢慢减小的，不是一个常量。
        for(int i = 0; i <  arr.length;i++){
            arr[i] = stack.pop().val;
        }
        return arr;
    }
}

二、剑指 Offer 24. 反转链表

要求：定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

解法1：使用栈+辅助头结点

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        while(head!=null){
            stack.push(head);
            head = head.next;
        }
        ListNode newHead = null;
        ListNode headInfo = null;
        while(stack.size()!=0){
            if(newHead == null){
                newHead = stack.pop();
                headInfo = newHead;
                continue;
            }
            ListNode temp = stack.pop();
            temp.next = newHead.next;
            newHead.next = temp;
            newHead = newHead.next;
        }
        return headInfo;

    }
}

解法二：直接使用头插法

具体思路：腾讯面试题-单链表的头插法

代码：

/**
 * 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 newHead = new ListNode(-1);
        while(head!=null){
            ListNode temp = head;
            head = head.next;
            temp.next = newHead.next;
            newHead.next = temp;
        }
        return newHead.next;

        
    }
}

使用头插法简洁，时间复杂度也小。注意要先移动head指针，保存该结点下一个结点的地址，再使用temp指针插入辅助的链表。

三、剑指 Offer 35. 复杂链表的复制

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

思路：通过Hashmap来实现。

/*
// 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 {
    HashMap<Node,Node> NodeList = new HashMap<>();
    public Node copyRandomList(Node head) {
        // 如果这个结点是空结点了，那就直接返回null。
        if(head == null){
            return null;
        }
        // 如果hashmap中没有这个结点
        if(!NodeList.containsKey(head)){
            // 这个结点的信息（包括结点地址，值，random和next，主要是地址）保存到Key。
            // 通过这个节点的值创建一个新的结点newHead。
            // 将newHead添加到map的value中。通过递归，添加next和random，生成链。
            // 递归的出口就是当next或者random的下一个都是null的时候，说明已经没有下一个，或者已经没有关联的random了
            // 直接返回null结束递归，一条完整的链就生成了。value指向的是下一个结点的key。
            Node newHead = new Node(head.val);
            NodeList.put(head,newHead);
            newHead.next = copyRandomList(head.next);
            newHead.random = copyRandomList(head.random);
        }
        return NodeList.get(head);
    }
}