链表（简单）

剑指 Offer 06. 从尾到头打印链表
剑指 Offer 24. 反转链表
剑指 Offer 35. 复杂链表的复制

剑指 Offer 06. 从尾到头打印链表 - 力扣（LeetCode）

单链表的定义：

/*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<>();
        ListNode cur=head;
        while(cur!=null){
    
            stack.push(cur);
            cur=cur.next;
        }
        int[] arr=new int[stack.size()];
        for(int i=0;i<arr.length;i++){
    
            arr[i]=stack.pop().val;
        }
        return arr;
    }
}
/** 复杂度分析： 时间复杂度 O(N) 空间复杂度 O(N) */

class Solution {
    
    public int[] reversePrint(ListNode head) {
    
        LinkedList<Integer> stack = new LinkedList<Integer>();
        while(head != null) {
    
            stack.addLast(head.val);//addLast()方法用于在LinkedList的末尾插入特定元素
            head = head.next;
        }
        int[] res = new int[stack.size()];
        for(int i = 0; i < res.length; i++)
            res[i] = stack.removeLast();//removeLast()方法用于从LinkedList中删除最后一个元素
    return res;
    }
}

/** 复杂度分析： 时间复杂度 O(N)：入栈和出栈共使用O(N)时间。 空间复杂度 O(N)：辅助栈stack和数组res共使用O(N)的额外空间 */

二：递归法

算法流程：

• 递推阶段： 每次传入 head.next ，以 head == null（即走过链表尾部节点）为递归终止条件，此时直接返回。
• 回溯阶段： 层层回溯时，将当前节点值加入列表，即tmp.add(head.val)。
  最终，将列表 tmp 转化为数组 res ，并返回即可。

复杂度分析

• 时间复杂度 O(N)： 遍历链表，递归 N 次。
• 空间复杂度 O(N)：系统递归需要使用 O(N) 的栈空间。

class Solution {
    
    ArrayList<Integer> tmp = new ArrayList<Integer>();
    public int[] reversePrint(ListNode head) {
    
        recur(head);
        int[] res = new int[tmp.size()];
        for(int i = 0; i < res.length; i++)
            res[i] = tmp.get(i);
        return res;
    }
    void recur(ListNode head) {
    
        if(head == null) return;
        recur(head.next);
        tmp.add(head.val);
    }
}

三：

class Solution {
    
    // 执行用时 : 0 ms, 在所有 Java 提交中击败了 100.00% 的用户
    // 内存消耗 : 39.8 MB, 在所有 Java 提交中击败了 100.00% 的用户
    // 不使用栈，不使用递归，反正怎么样也是扫描两趟，为什么要额外分配空间呢？
    public static int[] reversePrint(ListNode head) {
    
        ListNode node = head;
        int count = 0;
        while (node != null) {
    
            ++count;
            node = node.next;
        }
        int[] nums = new int[count];
        node = head;
        for (int i = count - 1; i >= 0; --i) {
    
            nums[i] = node.val;
            node = node.next;
        }
        return nums;
    }
}

剑指 Offer 24. 反转链表 - 力扣（LeetCode）

一：迭代

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
class Solution {
    
    public ListNode reverseList(ListNode head) {
    
        if(head==null || head.next==null) return head;
        ListNode pre=null;
        ListNode cur=head;
        ListNode tmp=null;
        while(cur!=null){
    
            tmp=cur.next;// 暂存后继节点 cur.next
            cur.next=pre;// 修改 next 引用指向
            pre=cur;// pre 暂存 cur
            cur=tmp;// cur 访问下一节点
        }
        return pre;
    }
}

二：递归

class Solution {
    
    public ListNode reverseList(ListNode head) {
    
        return recur(head, null);    // 调用递归并返回
    }
    
    private ListNode recur(ListNode cur, ListNode pre) {
    
        if (cur == null){
    
            return pre; // 终止条件
        } 
        ListNode res = recur(cur.next, cur);  // 递归后继节点
        cur.next = pre;              // 修改节点引用指向
        return res;                  // 返回反转链表的头节点
    }
}

剑指 Offer 35. 复杂链表的复制 - 力扣（LeetCode）

一：哈希表

/* // 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 {
    
    public Node copyRandomList(Node head) {
    
        Map<Node, Node> m = new HashMap<>();
        Node p = head;
        while(head != null) {
    
            Node t = new Node(head.val);
            m.put(head, t);
            head = head.next;
        }
        head = p;
        //根据原链表，查找哈希表将新链表连起来
        while(head != null) {
    
            Node n = head.next; //原始节点的下一个节点
            Node r = head.random;//原始节点随机节点
            //新节点的next指向下一个新节点
            m.get(head).next = m.get(n);
            //设置新节点的random结点指向
            m.get(head).random = m.get(r);
            head = head.next;
        }
        return m.get(p);
    }
}

class Solution {
    
    public Node copyRandomList(Node head) {
    
        if(head == null) return null;
        Node cur = head;
        Map<Node, Node> map = new HashMap<>();
        //复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射
        while(cur != null) {
    
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        //构建新链表的 next 和 random 指向
        while(cur != null) {
    
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        //返回新链表的头节点
        return map.get(head);
    }
}