[数据结构与算法]剑指Offer2

剑指Offer第二天

题1：从尾到头打印链表

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

简单题，一遍过，听到从尾到头，就想到要用栈来解决

class Solution {
    public int[] reversePrint(ListNode head) {
        ListNode cur = head;
        Stack<Integer> stack = new Stack<>();
        while(cur != null){
            stack.push(cur.val);
            cur = cur.next;
        }
        int size = stack.size();
        int[] a = new int[size];
        for(int i = 0; i < size; i++){
            a[i] = stack.pop();
        }
        return a;
    }
}

题2：反转链表（经典题）

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

这道题必知必会，考的频率太高了！

class Solution {
    public ListNode reverseList(ListNode head) {
        //dummyHead：虚拟头结点，这里表示最后指向的null
        //cur：当前的节点
        //next：存储原本的cur.next,防止反转后丢失
        ListNode dummyHead = null, cur = head;
        while(cur != null){
           //存储原先的cur.next
           ListNode next = cur.next;
           //反转
           cur.next = dummyHead;
           
           //初始化下一节点
           dummyHead = cur;
           cur = next; 
        }
        return dummyHead;
    }
}

题3：复杂链表的复制

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

原本是用容器存储random值

后面参照这个题解，重写了代码

https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/solution/jian-zhi-offer-35-fu-za-lian-biao-de-fu-zhi-ha-xi-/

能够让空间复杂度从O(N)降为O(1)，原地复制…

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null)return head;
        Node cur = head;
        //A->B->C的链表构造成A->NEWA->B->NEWB->C->NEWC
        while(cur != null){
            Node newNode = new Node(cur.val);
            //放置新节点位置
            newNode.next = cur.next;
            cur.next = newNode;

            //更新指针指向
            cur = cur.next.next;
        }

        //随机指针复制,新节点就用于
        cur = head;
        while(cur != null){
            if(cur.random != null){
                //NEWA的random = NEWRANDOM
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }

        //分离链表
        //复制的链表头
        Node copyHead = head.next;

        //cur指向原链表头结点
        cur = head;
        //curCopy指向新建链表头结点
        Node curCopy = head.next;
        //根据cur，curCopy分离出原链表和新建链表
        while(cur != null){
            cur.next = cur.next.next;
            cur = cur.next;
            if(curCopy.next != null){
                curCopy.next = curCopy.next.next;
                curCopy = curCopy.next;
            }
        }
        //返回新建链表，因为random的逻辑都是在新建链表上绑定的
        return copyHead;
    }
}