【剑指offer第二天】链表

清疚 2022-09-03 07:21 163阅读 0赞

## 题目一 从尾到头打印链表 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxMjYwOQ_size_16_color_FFFFFF_t_70]

### 方法一 利用栈 ###

借助栈存储，再从栈中弹出存到数组中

class Solution { 
        public int[] reversePrint(ListNode head) { 
            Deque<Integer> tmp = new LinkedList<>();
            while(head!=null){ 
                tmp.push(head.val);
                head = head.next;
            }
            int l = tmp.size();
            int []res = new int[l];
            for(int i = 0;i < l;i++){ 
                res[i] = tmp.pop();
            }
            return res;
        }
    }

### 方法二 递归 ###

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

### 题目二 反转链表 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxMjYwOQ_size_16_color_FFFFFF_t_70 1]

### 题目三 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxMjYwOQ_size_16_color_FFFFFF_t_70 2]  
深度复制，首先遍历链表在哈希表中存储结点的值，之后再次遍历链表，对新建的结点的next和random进行赋值

class Solution { 
        public Node copyRandomList(Node head) { 
            if(head == null) return null;
            Node cur = head;
            Map<Node,Node> map = new HashMap<>();
            while(cur != null){ 
                map.put(cur,new Node(cur.val));
                cur = cur.next;
            }
            cur = head;
            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);
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxMjYwOQ_size_16_color_FFFFFF_t_70]: /images/20220829/693bcb0da549428da3ac17856e5e9028.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxMjYwOQ_size_16_color_FFFFFF_t_70 1]: /images/20220829/ccde49e9916948beafa5a7a2d7bad037.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxMjYwOQ_size_16_color_FFFFFF_t_70 2]: /images/20220829/79725f7e213d45fa848bb42c6767a532.png