第2天 链表（简单）

剑指 Offer 06. 从尾到头打印链表

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

示例 1：

输入：head = [1,3,2]
输出：[2,3,1]

限制：

0 <= 链表长度 <= 10000

题解

逐次遍历链表,并将val放入辅助栈中,再对辅助栈进行出栈,将结果保存在一个数组中

/**
 * 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> stack = new Stack<Integer>();
        while(head != null){
            stack.push(head.val);
            head = head.next;
        }
        
        int size = stack.size();
        int[] res = new int[size];
        System.out.println(res.length);
        for(int i = 0; i < size; i++)
            res[i] = (int)stack.pop();
        return res;
    }
}

注:

stack.size()方法的返回值表示stack栈的大小,当出栈后,size()的返回值就会发生改变,所以应该用一个变量size记录stack的大小,而不是直接使用stack.size()

剑指 Offer 24. 反转链表

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

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

限制：

0 <= 节点个数 <= 5000

注意：本题与主站 206 题相同：https://leetcode-cn.com/problems/reverse-linked-list/

题解

思路一

正好上一题使用stack实现了从尾到头打印链表,所以沿用上一题的算法:

/**
 * 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<ListNode>();
        if(head == null)
            return null;
        while(head != null){
            stack.push(head);
            head = head.next;
        }
        ListNode res, temp;
        res = stack.pop();
        temp = res;
        temp.next = null;
        while(!stack.isEmpty()){
            temp.next = stack.pop();
            temp = temp.next;
            temp.next = null;
        }
        return res;
    }
}

思路二

双指针

1. 复制head指向的节点,使用temp指代;
2. temp的下一个节点为NULL;
3. head指针向后移动;
4. 再声明一个pre指针指向temp;
5. 当head不是空链表时:
   1. 复制head指向的节点,使用temp1指代;(这里编译器说temp已经使用过了,不能再用了;但其实temp已经没用了,覆盖了也没事)
   2. temp1的下个节点指向pre;(这一步将head指向的节点接在了新链表的头)
   3. 更新pre
   4. head指针向后移动

循环体中的语句其实与前面的语句功能很相似,但为了让第一个节点的next为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) {
        Stack<ListNode> stack = new Stack<ListNode>();
        if(head == null)
            return null;
        ListNode temp = new ListNode(head.val);
        temp.next = null;
        head = head.next;
        ListNode pre = temp;
        while(head != null){
            ListNode temp1 = new ListNode(head.val);
            temp1.next = pre;
            pre = temp1;
            head = head.next;
        }
        return pre;
    }
}

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

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

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

示例 3：

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

示例 4：

输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。

提示：

-10000 <= Node.val <= 10000
Node.random 为空（null）或指向链表中的节点。
节点数目不超过 1000 。

注意：本题与主站 138 题相同：https://leetcode-cn.com/problems/copy-list-with-random-pointer/

题解

一开始没理解懂题意,写的脑残代码,next和random字段是不能直接复制的,要不指向的就是原链表的各个节点了.这题简单理解就是深拷贝还是参考了官网题解,递归或者叫回溯,解决的真的很巧啊,法二更是秀了我一脸.

我就记录一下使用map记录映射的方法吧:

使用map,将旧节点与新节点做了映射.因为旧节点为key,所以复制的时候,只有一个对应的新节点会被创建,并与旧节点做映射,而headNew的next和random字段都是通过递归函数赋值的.

/*
// 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);
    }
}

看到有位叫eipip1e0的同学写的代码感觉更好理解一些,我就臭不要脸的放这里记录一下了:

class Solution {
    private Map<Node,Node> map = new HashMap<>();
    public Node copyRandomList(Node head) {
        // 终止条件next给过来的node为null；
        if(head == null){
            return null;
        }
        // 中间处理方法
        // 1. 递归创建节点到最后一个节点，并吧所有创建的节点保存在map中；
        Node newNode = new Node(head.val);
        map.put(head,newNode);
        newNode.next = copyRandomList(head.next);
        // 2. 因为递归过程中会创建所有的节点，所以回溯过程中直接进行newNode.random赋值
        newNode.random = map.get(head.random);
        return newNode;
    }
}