【搞定左神算法初级班】第3节：栈、队列、链表、矩阵结构及相关常见面试题

淡淡的烟草味﹌ 2022-02-28 12:48 126阅读 0赞

### **目  录：** ###

**一、栈**

题目1：用固定的大小的数组实现栈和队列

题目2：能返回栈中最小元素的栈

题目3：如何仅用队列结构实现栈结构？

**二、队列**

题目1：如何仅用栈结构实现队列结构？

题目2：猫狗队列

**三、链表**

题目1：反转单向和双向链表

题目2：给出两个有序链表的头结点，打印出两个链表中相同的元素

题目3：判断一个链表是否为回文结构

题目4：将单向链表按某值划分成左边小、中间相等、右边大的形式【荷兰国旗问题】

题目5：复制含有随机指针节点的链表

题目6：两个单链表相交的一系列问题【重点：很有意思】

**四、矩阵的打印和旋转**

题目1：顺时针打印矩阵

题目2：将一个正方形顺时针旋转90度

题目3：之字形打印矩阵

题目4：在一个行和列都有序的m行n列的矩阵中查找一个数是否存在

--------------------

# 一、栈 #

### 题目1：用固定的大小的数组实现栈和队列 ###

*  **固定大小的数组实现栈结构**

package com.offer.class3;
    
    /**
     * 固定数组实现栈结构
     */
    public class StackWithArray {
    
        private int[] arr;
        private int index;   // 指向即将放入元素的位置
    
        public StackWithArray(int initialSize){
            if(initialSize < 0){
                throw new IllegalArgumentException("the init size is less than 0");
            }
            arr = new int[initialSize];
            index = 0;
        }
    
        // 压栈
        public void push(int obj){
            if(index == arr.length){
                throw new ArrayIndexOutOfBoundsException("the stack is full!");
            }
            arr[index++] = obj;   // index指向的就是当前要存储数据的位置
        }
    
        // 弹栈（删除元素）
        public int pop(){
            if(index == 0){
                throw new ArrayIndexOutOfBoundsException("the stack is empty!");
            }
            return arr[--index];  // 删除的是index指向的前一个元素，因为index指向的是位置为空
        }
    
        // 弹出元素，但不删除
        public int peek(){
            if(index == 0){
                throw new ArrayIndexOutOfBoundsException("the stack is empty!");
            }
            return arr[index - 1];  // index并没有减小，所以index位置上的元素并没有删除
        }
    }

*  **固定大小的数组实现队列**

**注意：start、end、size 这三个变量的实际意义，size 变量实现了对 start 和 end 变量之间的解耦。**

package com.offer.class3;
    
    /**
     * 固定数组实现队列
     * 三个变量：start、end、size
     */
    public class QueueWithArray {
    
        private int start;  // 指向队头，每次要取数据的位置
        private int end;    // 指向队尾，每次要添加数据的位置
        private int size;   // 队列中元素的个数，利用size实现start和end之间的解耦
        private int[] arr;
    
        public QueueWithArray(int initialSize){
            if(initialSize < 0){
                throw new IllegalArgumentException("the initialSzie is less than 0");
            }
            arr = new int[initialSize];
            start = 0;
            end = 0;
            size = 0;
        }
    
        // 添加一个元素
        public void push(int obj){
            if(size == arr.length){
                throw new ArrayIndexOutOfBoundsException("the queue is full");
            }
            size++;
            arr[end] = obj;
            // 如果end指向数组中最后一个元素的位置，那么需要跳到开始的位置，从头开始
            end = (end == arr.length - 1) ? 0 : end + 1;
        }
    
        public int poll(){
            if(size == 0){
                throw new ArrayIndexOutOfBoundsException("the queue is empty");
            }
            size--;
            int tmp = start;
            start = (start == arr.length - 1) ? 0 : start + 1;
            return arr[tmp];
        }
    
    }

### 题目2：能返回栈中最小元素的栈 ###

实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。  
**要求：**

> 1．pop、push、getMin 操作的时间复杂度都是O(1)。  
> 2．设计的栈类型可以使用现成的栈结构。

思路：用一个额外的栈存储最小元素。

package com.offer.class3;
    
    import java.util.Stack;
    
    /**
     * 用一个额外的栈空间维持一个最小元素
     */
    public class MyStack {
    
        private Stack<Integer> dataStack;
        private Stack<Integer> minStack;
    
        public MyStack(){
            dataStack = new Stack<Integer>();
            minStack = new Stack<Integer>();
        }
    
        public void push(int obj){
            dataStack.push(obj);
            if(minStack.isEmpty()){
                minStack.push(obj);    // 当最小值栈为空时，直接将数存进去
            }else if(obj <= minStack.peek()){
                minStack.push(obj);    // 当obj小于等于最小值栈中的最小值时，直接压入栈中
            }else{
                minStack.push(minStack.peek());  // 将最小值栈中的最小值再压入一遍
            }
        }
    
        public int pop(){
            minStack.pop();
            return dataStack.pop();
        }
    
        public int getMin(){
            if(minStack.isEmpty()){
                throw new ArrayIndexOutOfBoundsException("the stack is empty!");
            }
            return minStack.peek();
        }
    }

### 题目3：如何仅用队列结构实现栈结构？ ###

*  原理：可以用两个队列（queue、help）来实现栈，加元素时加总是在queue；删除元素时，把 queue 最后一位前的元素全部弹出放入 help 队列中，然后再弹出返回 queue 的最后一位元素（这就达成栈后入先出的要求了），然后交换 help 和queue 指针即可
 *  队列：poll(移除并返回队列的头部)，add(添加一个元素到队列尾部)，peek（返回队列的头部，不删除）

package com.offer.class3;
    
    import java.util.LinkedList;
    import java.util.Queue;
    
    /**
     * 用两个栈实现队列
     */
    public class TwoQueueWithStack {
    
        private Queue<Integer> queue;
        private Queue<Integer> help;
    
        public TwoQueueWithStack(){
            // LinkedList实现了Queue接口
            queue = new LinkedList<Integer>();
            help = new LinkedList<Integer>();
        }
    
        // 插入一个元素
        public void push(int obj){
            // 插入元素永远都是插入到queue中
            queue.add(obj);
        }
    
        // 删除一个元素
        public int pop(){
            if(queue.isEmpty()){
                throw new RuntimeException("stack is empty!");
            }
            while(queue.size() > 1){
                // 将queue中除最后一个元素外，全部弹出添加到help中
                help.add(queue.poll());
            }
            int res = queue.poll();
            swap();
            return res;
        }
    
        // 弹出一个元素（不删除）
        public int peek(){
            if(queue.isEmpty()){
                throw new RuntimeException("stack is empty!");
            }
            while(queue.size() > 1){
                // 将queue中除最后一个元素外，全部弹出添加到help中
                help.add(queue.poll());
            }
            int res = queue.poll();
            help.add(res);
            swap();
            return res;
        }
    
        // 互换queue和help的指针,help只是辅助队列，始终操作的还是queue
        public void swap(){
            Queue<Integer> temp = help;
            help = queue;
            queue = temp;
        }
    }

--------------------

# 二、队列 #

### 题目1：如何仅用栈结构实现队列结构？ ###

*  原理：可以用两个栈（stack1和stack2）来实现队列 ，进入时放入stack1栈，出栈时从stack2栈出，这样就能把顺序变为先进先出,( 栈：push,pop,peek)

**需要注意的点：**

*  1、只有当stack2为空时，stack1才能往stack2中放数据，不然顺序就会乱了；
 *  2、如果stack1要往stack2中放数据，肯定是一次性将stack1中的数据全部放到stack2中。

package com.offer.class3;
    
    import java.util.Stack;
    
    /**
     * 用两个栈实现队列
     */
    public class TwoStackWithQueue {
    
        Stack<Integer> stack1 = new Stack<Integer>();
        Stack<Integer> stack2 = new Stack<Integer>();
    
        // 添加元素
        public void add(int obj){
            stack1.push(obj);
        }
    
        // 删除元素
        public int poll(){
            if(stack2.isEmpty() && stack1.isEmpty()){
                throw new RuntimeException("queue is empty!");
            }else if(stack2.isEmpty()){
                while(!stack1.isEmpty()){
                    // stack2如果为空，则stack1中的元素全部倒进stack2中
                    stack2.push(stack1.pop());
                }
            }
            // 如果stack2中有元素，则直接弹出。只有当stack2为空时，才会从stack1中往stack2中放数据，而且肯定是一次性放完
            return stack2.pop();
        }
    
        // 弹出元素，不删除
        public int peek(){
            if(stack2.isEmpty() && stack1.isEmpty()){
                throw new RuntimeException("queue is empty!");
            }else if(stack2.isEmpty()){
                while(!stack1.isEmpty()){
                    // stack2如果为空，则stack1中的元素全部倒进stack2中
                    stack2.push(stack1.pop());
                }
            }
            // 弹出stack2中最上面的元素，即实现了队列的先进先出
            return stack2.peek();   // 前面的和poll一样，只不过最后需要返回而不是删除
        }
    }

### 题目2：猫狗队列 ###

宠物、狗和猫的类如下：
    public class Pet { private String type; }
    public Pet(String type) { this.type = type; }
    public String getPetType() { return this.type; }
    }
    public class Dog extends Pet { public Dog() { super("dog"); } }
    public class Cat extends Pet { public Cat() { super("cat"); } }
    
    实现一种狗猫队列的结构，要求如下： 
    用户可以调用add方法将cat类或dog类的实例放入队列中； 
    用户可以调用pollAll方法，将队列中所有的实例按照进队列的先后顺序依次弹出； 
    用户可以调用pollDog方法，将队列中dog类的实例按照进队列的先后顺序依次弹出； 
    用户可以调用pollCat方法，将队列中cat类的实例按照进队列的先后顺序依次弹出； 
    用户可以调用isEmpty方法，检查队列中是否还有dog或cat的实例；
    用户可以调用isDogEmpty方法，检查队列中是否有dog类的实例； 
    用户可以调用isCatEmpty方法，检查队列中是否有cat类的实例。

*  **分析：**

1、建一个猫狗队列类，这个类里包含 DogQueue 和 CatQueue 两个队列，用于分别加猫和加狗，但这个会导致在pollAll时无法判断之前猫狗的顺序，所以有了第2步；  
2、建一个 CatDog 类，里面包含 pet 和 count 两个成员，pet 用于记录 CatDog 类的这个实例是猫还是狗，count 用于记录当前 pet 的顺序，count小的在前面，那么就能判断猫狗的顺序了。

package com.offer.class3;
    
    import java.util.LinkedList;
    import java.util.Queue;
    
    /**
     * 猫狗队列问题
     */
    public class CatDogQueue {
    
        public static class Pet{
            private String type;
    
            public Pet(String type){
                this.type = type;
            }
    
            public String getPetType(){
                return this.type;
            }
        }
    
        public static class Dog extends Pet{
            public Dog(){
                super("dog");
            }
        }
    
        public static class Cat extends Pet{
            public Cat(){
                super("cat");
            }
        }
    
        public static class CatDog{
            private Pet pet;     // 用于记录是猫还是狗
            private long count;  // 用于记录当前pet的顺序
    
            public CatDog(Pet pet, long count){
                this.pet = pet;
                this.count = count;
            }
    
            public Pet getPet(){
                return this.pet;
            }
    
            public long getCount(){
                return this.count;
            }
        }
    
        // CatDogQueue 的正式代码
        private Queue<CatDog> catQueue = new LinkedList<CatDog>();   // 猫队列
        private Queue<CatDog> dogQueue = new LinkedList<CatDog>();   // 狗队列
        private long count = 0;
    
        // 增加元素
        public void add(Pet pet){
            if(pet.getPetType().equals("cat")){
                catQueue.add(new CatDog(pet, count++));
            }else if(pet.getPetType().equals("dog")){
                dogQueue.add(new CatDog(pet, count++));
            }else{
                throw new RuntimeException("error : this is not cat or dog type!");
            }
        }
    
        // 弹出所有元素
        public Pet pollAll(){
            if(!catQueue.isEmpty() && !dogQueue.isEmpty()){
                if(catQueue.peek().count < dogQueue.peek().count){
                    // 如果猫队列的第一个元素顺序在狗队列第一个元素之前，则弹出猫队列第一个元素
                    return catQueue.poll().getPet();
                }else{
                    return dogQueue.poll().getPet();
                }
            }else if(!catQueue.isEmpty()){
                return catQueue.poll().getPet();
            }else if(!dogQueue.isEmpty()){
                return dogQueue.poll().getPet();
            }else{
                throw new RuntimeException("error : queue is empty!");
            }
        }
    
        // 弹出狗猫列元素
        public Cat pollCat(){
            if(catQueue.isEmpty()){
                throw new RuntimeException("error : the cat queue is empty!");
            }else{
                return (Cat) catQueue.poll().getPet();
            }
        }
    
        // 弹出狗队列元素
        public Dog pollDog(){
            if(dogQueue.isEmpty()){
                throw new RuntimeException("error : the dog queue is empty!");
            }else{
                return (Dog) dogQueue.poll().getPet();
            }
        }
    
        public boolean isAllEmpty(){
            return dogQueue.isEmpty() && catQueue.isEmpty();
        }
    
        public boolean isDogQueueEmpty(){
            return dogQueue.isEmpty();
        }
    
        public boolean isCatQueueEmpty(){
            return catQueue.isEmpty();
        }
    }

*  关于猫狗队列问题，可以好好体会下设计的思想。

--------------------

# 三、链表 #

### 题目1：反转单向和双向链表 ###

*  **反转单向链表**
 *  【题目】 分别实现反转单向链表和反转双向链表的函数。
 *  【要求】 如果链表长度为N，时间复杂度要求为O(N)，额外空间 复杂度要求为O(1)
 *  【分析】从头到尾一个结点一个结点的挨个处理：将当前结点（head） 和下一个结点断开，指向前一个结点

剑指offer中的原题：[https://blog.csdn.net/pcwl1206/article/details/85938437][https_blog.csdn.net_pcwl1206_article_details_85938437]

为了正确的反转一个链表，需要调整链表中指针的方向。为了将调整指针这个复杂的过程分析清楚，我们可以借助图形来直观的分析。在图中所示的链表中，h, i, j是3个相邻的结点。假设经过若干的操作，我们已经把结点h之前的指针调整完毕，这些结点的next都指向前面的一个结点。接下来我们把i的next指向h，此时的链表结构如图b所示。

![20190326142136888.png][]

不难注意到，由于结点 i 的next指向了它的前一个结点，导致我们无法在链表中遍历到结点 j。为了避免链表在结点 i 处断开，我们需要在调整结点 i 的next之前把结点 j 保存下来。

也就是说我们在调整结点 i 的 next 指针时，除了需要知道结点 i 本身之外，还需要知道 i 的前一个结点h，因为我们需要把结点 i 的next 指向结点 h，同时，我们还要事先保存 i 的下一个结点 j，以防止链表断开。因此相应地我们需要三个指针，分别指向当前遍历到的结点，它的前一个结点和后一个结点。

最后我们试着找到反转链表的头结点。不难分析出反转后的链表的头结点是原始链表的尾节点。什么结点是尾节点，自然是 next 为 null 的结点。

package com.offer.class3;
    
    /**
     * @author pengcheng
     * @date 2019-03-26 11:47
     * content：反转链表
     */
    public class ReverseLinkedList {
    
        public static class Node{
            public int value;
            public Node next;
    
            public Node(int value){
                this.value = value;
            }
        }
    
        public static Node reverseLinkedList(Node head){
            if(head == null){
                return null;
            }
    
            Node pre = null;    // 当前节点的前一个节点
            Node next = null;   // 当前节点的后一个节点
    
            while(head != null){
                // 先用next保存head的下一个节点的信息
                // 保证单链表不会因为失去head节点的原next节点而就此断裂
                next = head.next;
                // 保存完next，就可以让head从指向next变成指向pre了
                head.next = pre;
                // head指向pre后，就继续依次反转下一个节点
                // 让pre、head、next依次向后移动一个节点，继续下一个节点的指针反转
                pre = head;
                head = next;
            }
            // 如果head为null的时候，pre就为最后一个节点了，此时链表已经反转完毕，pre就是反转后链表的第一个节点
            return pre;
        }
    }

*  **反转双向链表**
 *  【分析】从头到尾一个结点一个结点的挨个处理：对每个结点，交换其next和pre即可，并记录当前的引用（仅仅为了最后的返回）

package com.offer.class3;
    
    /**
     * @author pengcheng
     * @date 2019-03-26 14:26
     * content：双向链表的反转
     */
    public class ReverseDoubleLinkedLsit {
    
        public static class DoubleNode{
    
            int val;
            DoubleNode pre;    // 指向前一个节点
            DoubleNode next;   // 指向后一个节点
    
            public DoubleNode(int value){
                this.val = value;
            }
        }
    
        public static DoubleNode reverseDoubleLinkedList(DoubleNode head){
            if(head == null){
                return null;
            }
    
            DoubleNode tmp = null;
            DoubleNode res = null;  // res的作用仅仅是记录head，因为最后一次循环后head为null，但是我们要返回最后一个不为null的head
    
            // 从头节点开始，依次往后挨个处理
            while(head != null){
                // pre和next指针互换
                tmp = head.next;
                head.next = head.pre;
                head.pre = tmp;
                res = head;     // 记录head节点
                head = tmp;     // 往后推进一个节点
            }
            return res;
        }
    }

### 题目2：给出两个有序链表的头结点，打印出两个链表中相同的元素 ###

*  类似于“荷兰国旗”问题

package com.offer.class3;
    
    /**
     * @author pengcheng
     * @date 2019-03-26 17:10
     * content：打印两个有序链表的公共部分
     */
    public class PrintCommonPart {
    
        public static class Node{
            int value;
            Node next;
    
            public Node(int value){
                this.value = value;
            }
        }
    
        public void printCommonPart(Node head1, Node head2){
            while (head1.next != null && head2.next != null){
                if(head1.value < head2.value){
                    head1 = head1.next;   // 链表1往后走
                }else if(head1.value > head2.value){
                    head2 = head2.next;   // 链表2往后走
                }else{
                    // head1.value = head2.val
                    System.out.print(head1.value + " ");
                    // head1和head2同时往后走一位，继续找相同的地方
                    head1 = head1.next;
                    head2 = head2.next;
                }
            }
        }
    }

### 题目3：判断一个链表是否为回文结构 ###

> 题目：给定一个链表的头节点 head，请判断该链表是否为回文结构（左右对称）。 例如： 1->2->1，返回 true。 1->2->2->1，返回 true。15->6->15，返回true。 1->2->3，返回 false。  
> 进阶： 如果链表长度为N，时间复杂度达到O(N)，额外空间复杂度达到O(1)。

*  分析：
 *  回文：理解1：原序和逆序一样 。 理解2：能从中间对折

**方法1：**isPalindrome1非进阶版：因为不需要空间O(1)，所以可以增加一个额外的空间O(N)，我们先遍历一次链表，把每个结点的值放入一个栈中，那么值弹出时就是原链表的逆序，所以只需要每弹出一个比较一个即可，若有不一样的，则直接返回false，否则就是回文。

**方法2：**可以对方法1进行改进，栈中只存储后一半的数据，然后依次弹出与链表的前半部分进行比较。空间复杂度减半。

**方法3：**isPalindrome2进阶版：空间复杂度O(1),总体上是先找到链表中点，再把后半部分反转，然后前后比较，一样则是回文。找中点用了快指针（一次两步）和慢指针（一次一步），若为偶数，慢指针指向两个中点的前一个，若为奇数，慢指针指向正中位置。判断完回文后要把后半部分再反转回去，不能说别人给你的数据，你把结构给别人改变了。

package com.offer.class3;
    
    import java.util.Stack;
    
    /**
     * @author pengcheng
     * @date 2019-03-26 17:47
     * content：判断一个链表是否是回文结构
     */
    public class IsPalindromList {
    
        public static class Node{
            int val;
            Node next;
    
            public Node(int val){
                this.val = val;
            }
        }
    
        // 方法1：用栈结构存储整个链表元素，再依次弹出与链表从头开始比较，空间复杂度为：O(n)
        public boolean isPalindromList1(Node head){
    
           if(head == null || head.next == null){
               return true;  // 没有节点或者只有一个节点时，肯定是回文链表
           }
    
            Node cur = head;
    
            Stack<Node> stack = new Stack<Node>();
            // 遍历链表，将链表元素从头开始依次亚入栈中
            while(cur != null){
                stack.push(cur);
                cur = cur.next;
            }
    
            // 开始比对栈中依次弹出的元素与链表从头开始遍历的元素是否都相等
            cur = head;
            while(cur != null){
                if(stack.pop() != cur){
                    return false;
                }
                cur = cur.next;
            }
            return true;
        }
    
        // 方法2：用栈只存储链表一半的元素（中间位置到最后），然后依次弹出与链表的前半部分比较
        // 空间复杂度为：O(n/2)
        // 代码略
    
        // 方法3：将链表对折，后半部分的链表反转与前半部分链表进行比较
        public boolean isPalindromList2(Node head){
            if(head == null || head.next == null){
                return true;  // 没有节点或者只有一个节点时，肯定是回文链表
            }
    
            Node cur = head;
            Node slow = head;  // 慢指针：一次走一个节点
            Node fast = head;  // 快指针：一次走两个节点
    
            // 元素总个数为奇数时，慢指针最后指向中间位置，若为偶数，则走到中间位置的前一位
            // 注意：在向后遍历的时候，需要判断快指针指向的节点是否为空，不然会出现异常
            while(fast.next != null && fast.next.next != null){
                fast = fast.next.next; // 若fast.next != null，那么说明这是偶数个
                slow = slow.next;
            }
    
            // slow 到达的是中点位置，反转后半部分，反转后中点指向的是null
            Node end = reverseSingleList(slow);
            fast = end;
            // 将前半部分与后半部分折叠对比
            while(cur != null && fast != null){
                if(cur.val != fast.val){
                    return false;
                }
                cur = cur.next;
                fast = fast.next;
            }
            // 不能改变原有的数据结构，所以还需要将后半部分反转还原过去
            cur = reverseSingleList(end);
            return true;
        }
    
        // 链表反转
        public Node reverseSingleList(Node head){
            Node pre = null;
            Node next = null;
    
            while(head != null){
                next = head.next;
                head.next = pre;
                // 往后推进一个节点
                pre = head;
                head = next;
            }
            return pre;
        }
    }

### 题目4：将单向链表按某值划分成左边小、中间相等、右边大的形式【荷兰国旗问题】 ###

*  【题目】 给定一个单向链表的头节点head，节点的值类型是整型，再给定一个 整数pivot。实现一个调整链表的函数，将链表调整为左部分都是值小于 pivot 的节点，中间部分都是值等于pivot的节点，右部分都是值大于 pivot的节点。 除这个要求外，对调整后的节点顺序没有更多的要求。 例如：链表9->0->4->5->1，pivot=3。 调整后链表可以是1->0->4->9->5，也可以是0->1->9->5->4。总 之，满足左部分都是小于3的节点，中间部分都是等于3的节点（本例中这个部 分为空），右部分都是大于3的节点即可。对某部分内部的节点顺序不做要求。
 *  **进阶**： 在原问题的要求之上再增加如下两个要求。
    
     *  在左、中、右三个部分的内部也做顺序要求，要求每部分里的节点从左到右的 顺序与原链表中节点的先后次序一致。 例如：链表9->0->4->5->1，pivot=3。 调整后的链表是0->1->9->4->5。 在满足原问题要求的同时，左部分节点从左到 右为0、1。在原链表中也是先出现0，后出现1；中间部分在本例中为空，不再 讨论；右部分节点 从左到右为9、4、5。在原链表中也是先出现9，然后出现4， 最后出现5。
     *  如果链表长度为N，时间复杂度请达到O(N)，额外空间复杂度请达到O(1)。
 *  【分析】：
    
     *  listPartition1非进阶版：不考虑稳定性和空间复杂度。所以可以遍历一遍链表存放在数组中，然后就是荷兰国旗问题，将数组划分为三段less，equal，more，再将数据转移到链表中。
     *  listPartition2进阶版：要求稳定性和空间复杂度O(1)，遍历链表时less、equal、more指向它们第一次出现的结点，用endless、endequal、endmore来添加结点，属于哪一个就加在哪一个的尾巴后面【保证了稳定性，因为less，equal，more指向的是各自范围出现的第一个】，最后再将less，equa，more三个链表链接在一起就可以了。

**基础版代码：**

package com.offer.class3;
    
    /**
     * @author pengcheng
     * @date 2019-03-26 21:22
     * content：链表的划分：小于、等于、大于
     */
    public class LinkedPartition {
    
        public static class Node{
            int val;
            Node next;
    
            public Node(int val){
                this.val = val;
            }
        }
    
        // 将链表中的元素先放进数组中，然后再进行划分
        public Node listPartition1(Node head, int num){
            if(head == null || head.next == null){
                return head;
            }
    
            int i = 0;
            Node cur = head;
    
            // 计算有多少个节点
            while(cur != null){
                i++;
                cur = cur.next;
            }
    
            int[] arr = new int[i];   // 申请一个和链表中元素个数相等的数组
    
            cur = head;
            i = 0;
            // 从链表头结点开始遍历，将节点的val存进数组中
            while(cur != null){
                arr[i++] = cur.val;
                cur = cur.next;
            }
            // 在数组中使用荷兰国旗的方法对值进行小、等于、大的区域划分
            arrPartition(arr, num);
    
            // 按照排好序的数组顺序，将对应val节点串起来
            cur = head;
            i = 0;
            while(cur != null){
                cur.val = arr[i++];
                cur = cur.next;
            }
            return head;
        }
    
        public void arrPartition(int[] arr, int num){
            int less = -1;
            int more = arr.length;
            int cur = 0;
            while(cur != more){
                if(arr[cur] < num){
                    // 当前数与最小区域边界后一个位置元素进行交换，cur指针推进一位
                    swap(arr, ++less, cur++);
                }else if(arr[cur] > num){
                    // 当前数与最大区域边界的前一个位置元素进行交换，cur指针不变
                    swap(arr, cur, --more);
                }else{
                    cur++;   // 等于时,cur自增
                }
            }
    
        }
    
        public void swap(int[] arr, int i, int j){
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }

**进阶版代码：**

package com.offer.class3;
    
    /**
     * @author pengcheng
     * @date 2019-03-26 21:42
     * content：链表划分的进阶版：时间复杂度：O(N) 空间复杂度：O(1)、保证稳定性
     */
    public class LinkedPartitionImproved {
    
        public static class Node{
            int val;
            Node next;
    
            public Node(int val){
                this.val = val;
            }
        }
    
        // 将一条
        public Node listPartition2(Node head, int num){
            Node less = null;       // 存放小于num的节点,指向第一次出现在该区域的节点
            Node equal = null;
            Node more = null;
            Node endless = null;
            Node endequal = null;   // 指向各自链表的结尾
            Node endmore = null;
            Node next = null;
    
            while(head != null){
                next = head.next;
                head.next = null;  // 每次加入的节点都是指向null，就是less、equal、more的末尾节点
                if(head.val < num) {
                    // 放入less区域
                    if (less == null) {
                        less = head;
                        endless = head;
                    } else {
                        endless.next = head;   // less区域的尾节点指针指向head
                        endless = head;        // 推进链表，将endless指针指向head节点
                    }
                }else if(head.val > num){
                    // 放入more区域
                    if(more == null){
                        more = head;
                        endmore = head;
                    }else{
                        endmore.next = head;
                        endmore = head;
                    }
                }else{
                    if(equal == null){
                        equal = head;
                        endequal = head;
                    }else{
                        endequal.next = head;
                        endequal = head;
                    }
                }
                head = head.next;
            }
    
            // 将划分好的三部分子链表串起来，返回
            // 需要考虑到可能某部分子链表可能不存在的情况
            if(less != null){
                endless.next = equal;     // less子链表存在
                if(equal != null){
                    endequal.next = more; // equal子链表存在
                }else{
                    endless.next = more;  // equal子链表不存在
                }
                return less;
            }else{
                // less子链表不存在
                if(equal != null){
                    endequal.next = more;
                    return equal;
                }else{
                    // equal子链表不存在，直接返回more子链表
                    return more;
                }
            }
        }
    }

### 题目5：复制含有随机指针节点的链表 ###

*  【题目】 一种特殊的链表节点类描述如下：

public class Node { 
        public int value; 
        public Node next; 
        public Node random;
        public Node(int data) {
             this.value = data;
         }
    }

Node类中的value是节点值，next指针和正常单链表中next指针的意义一样，都指向下一个节点，random指针是Node类中新增的指针，这个指针可能指向链表中的任意一个节点，也可能指向null。 给定一个由Node节点类型组成的无环单链表的头节点head，请实现一个函数完成这个链表中所有结构的复制，并返回复制的新链表的头节点。

**进阶**：不使用额外的数据结构，只用有限几个变量，且在时间复杂度为 O(N)内完成原问题要实现的函数。

*  【分析】：
    
     *  copyListWithRand1 非进阶版：利用一个hashmap实现原链表结点和复制结点的映射，然后就可以把结构关系复制下来了。要想知道复制链表节点之间的对应关系，可以通过查找原节点之间的关系得到。比如：想得到A'和B'之间的关系，可以通过A找到B，再B.get()找到B'。
     *  copyListWithRand2 进阶版：因为要求不使用额外的数据结构，即不能用 hashmap，只用链表，步骤如下：
        
         *  1、复制结点到链表，成为1->1'->2->2'->3->3'->...->null形式；
         *  2、复制rand结构
         *  3、将链表拆分出来，得到原链表和复制链表。

**非进阶版代码实现： **

package com.offer.class3;
    
    import java.util.HashMap;
    
    /**
     * @author pengcheng
     * @date 2019-03-27 09:03
     * content：拷贝一个带有random节点的链表
     */
    public class CopyListWithRandom {
    
        public static class Node{
            int value;
            Node next;
            Node random;    // 指向链表中任一节点或者null
    
            public Node(int value){
                this.value = value;
            }
        }
    
        // 利用hashmap来进行元素列表节点和复制节点之间的映射，key存原节点，value存对应的复制节点
        public Node copyListWithRandom1(Node head){
            // hashmap的key和value存的都是Node类型
            HashMap<Node,Node> map = new HashMap<Node, Node>();
    
            Node cur = head;
            // 第一次遍历：拷贝节点,形成节点之间的映射关系
            while(cur != null){
                map.put(cur, new Node(cur.value));
                cur = cur.next;
            }
    
            cur = head;
            // 第二次遍历：复制节点之间的关系，即：next和random指针
            // 原链表节点之间的指针关系是知道的，比如想知道A'和B'之间的关系，可以通过:A->B->B',这样就找到了B'
            while(cur != null){
                // key为cur的value节点的next指针指向的是key为cur.next对应的value节点
                map.get(cur).next = map.get(cur.next);
                // key为cur的value节点的random指针指向的是key为cur.random对应的value节点
                map.get(cur).random = map.get(cur.random);
                cur = cur.next;
            }
            return map.get(head);  // 返回复制链表的头结点
        }
    
    }

**进阶版代码实现：**

package com.offer.class3;
    
    /**
     * @author pengcheng
     * @date 2019-03-27 09:31
     * content：拷贝含有random节点链表的进阶版
     */
    public class CopyListWithRandomImproved {
    
        public static class Node{
            int value;
            Node next;
            Node random;    // 指向链表中任一节点或者null
    
            public Node(int value){
                this.value = value;
            }
        }
    
        public Node copyListWithRandom2(Node head){
            if(head == null){
                return null;
            }
    
            Node cur = head;
            Node tmp = null;
            // 拷贝节点，重建链表结构为：1->1'->2->2'->3->3'->...->null形式
            // 即将拷贝的节点直接关联到原节点的next指针上
            while(cur != null){
                tmp = head.next;                 // 先将当前指针原链表中的下一个节点保存起来
                cur.next = new Node(cur.value);  // 将当前节点复制的节点设置为当前节点的next节点
                cur.next.next = tmp;             // 将原节点的next节点设置为员节点拷贝节点的next节点
                cur = cur.next.next;
            }
    
            cur = head;
            Node curCopy = head.next;
            // 复制random结构
            while(cur != null){
                curCopy = cur.next;
                // 拷贝节点的random节点就是cur的random节点的后一个节点
                curCopy.random = (cur.random == null) ? null : cur.random.next;
                cur = cur.next.next;
            }
    
            Node headCopy = head.next;
            cur = head;
            // 拆分链表
            while(cur != null){
                curCopy = cur.next;
                cur.next = cur.next.next;   // 走两个next
                curCopy.next = curCopy.next == null ? null : curCopy.next.next;
                cur = cur.next;  // 推进节点
            }
            return headCopy;
        }
    }

### 题目6：两个单链表相交的一系列问题 ###

> 【题目】 在本题中，单链表可能有环，也可能无环。给定两个单链表的头节点 head1和head2，这两个链表可能相交，也可能不相交。请实现一个函数， 如果两个链表相交，请返回相交的第一个节点；如果不相交，返回null 即可。
> 
> **进阶：**要求：如果链表 1 的长度为N，链表 2 的长度为 M，时间复杂度请达到 O(N+M)，额外空间复杂度请达到O(1)。
> 
> **注意：两个节点相交指的是内存地址相等，而不是值相等。**

*  【分析】：这道题实际是三道题的综合，要解决以下三个问题：【以下是基础版，进阶版（不使用HashSet)】
    
     
    
     *  (1)、单链表是否有环，有环则返回入环结点，否则null
     *  (2)、两个无环单链表是否相交，相交则返回相交的第一个结点，否则null
     *  (3)、两个有环单链表是否相交，相交则返回相交的第一个结点，否则null
 *  **主函数：**

public class FindFirstIntersectNode {
    
        public static class Node{
            int value;
            Node next;
    
            public Node(int value){
                this.value = value;
            }
        }
    
        // 主函数
        public Node findFirstIntersectNode(Node head1, Node head2){
            if(head1 == null || head2 == null){
                return null;
            }
    
            // 判断单链表是否有环，若有环则返回入环节点，否则返回null
            Node loop1 = getLoopNode(head1);
            Node loop2 = getLoopNode(head2);
    
            if(loop1 == null && loop2 == null){
                // 判断两个无环链表是否相交，相交则返回相交的第一个节点，不相交则返回null
                return noLoop(head1, head2);
            }else if(loop1 != null && loop2 != null){
                // 判断两个有环链表是否相交，相交则返回相交节点，否则返回null
                return bothLoop(head1, loop1, head2, loop2);
            }
            return null;  // 一个有环，一个无环，不可能相交，则直接返回null
        }
    }

*  **单链表是否有环，有环则返回入环结点，否则null**

思路1：使用hashset存储遍历过的节点，每次存储前，都先查询下给节点是否存在，如果存在则存在环；

思路2：使用两个指针，快指针一次走两步，慢指针一次走一步。当两个指针相遇时，快指针回到起点一次走一步，慢指针在相遇的节点处继续往下一次走一步，将会在环的入口节点处相遇。

思路2其实是剑指offer上的解题思路：[https://blog.csdn.net/pcwl1206/article/details/85931023][https_blog.csdn.net_pcwl1206_article_details_85931023]

// 1.检查单链表是否有环：利用HashSet去重的特性完成
    public Node getLoopNode(Node head){
        HashSet<Node> set = new HashSet<>();
        while(head != null){
            if(!set.contains(head)){
                set.add(head);     // 若head节点不在set里，则add进去
                head = head.next;  // 向后推进链表
            }else{
                // 到这里说明head节点在set里已经存在了，即有环，此节点即为环的入口节点
                return head;
            }
        }
        return null;
    }

*  **两无环单链表是否相交**

// 2.两无环单链表是否相交，相交则返回相交的第一个节点，不相交返回null
    public Node noLoop(Node head1, Node head2){
        HashSet<Node> set = new HashSet<>();
        // 将head1链表放入set中
        while(head1 != null){
            set.add(head1);
            head1 = head1.next;
        }
        // 遍历head2链表，与set集合中的head1链表的节点进行比较，看是否有相等的
        while(head2 != null){
            if(set.contains(head2)){
                return head2;
            }
            head2 = head2.next;
        }
        return null;   // 遍历完head2都没有与head1有重复的节点，说明不相交
    }

*  **两有环单链表是否相交 **

如下图所示可以分为三种情况：

// 3.两有环链表是否相交
    public Node bothLoop(Node head1, Node loop1, Node head2, Node loop2){
        // 环外相交：可归结为无环单链表找相交点
        if(loop1 == loop2){
            HashSet<Node> set = new HashSet<>();
            while(head1 != loop1){
                // 遍历head1环以外的节点
                set.add(head1);
                head1 = head1.next;
            }
            while(head2 != loop2){
                // 将head2环外的节点与head1环外的节点进行对比，看是否有相等的
                if(set.contains(head2)){
                    return head2;
                }
                head2 = head2.next;
            }
            return loop1;
        }else{
            // 两个6形式无相交 + 环内相交（不同的环入口点）
            Node cur = loop1.next;
            while(cur != loop1){
                // cur从loo1开始在环中向下遍历，若直到再次遍历到loop1位置处，也没有遇到loop2，则说明二者不相交
                if(cur == loop2){
                    return loop1;   // 遇见了loop2，则说明相交，即为环内相交的情况
                }
                cur = cur.next;
            }
            return null;  // cur遍历完它自己那个环都没有遇到loop2，则说明不相交，即为两个6的情况
        }
    }

--------------------

# 四、矩阵的打印和旋转 #

### 题目1：顺时针打印矩阵 ###

思路：左上角元素和右下角元素可以组成一个矩阵。每次打印都是从左上角打印。打印完外圈，打印内圈。

![20190326100648197.png][]

package com.offer.class3;
    
    /**
     * 打印矩阵问题
     */
    public class PrintMatrix {
    
        public void printMatrix(int[][] matrix){
            int lr = 0;
            int lc = 0;
            int rr = matrix.length - 1;
            int rc = matrix[0].length - 1;
    
            // 左上角的横纵坐标有一个大于等于右下角的横纵坐标的时候就停止打印
            while(lr <= rr && lc <= rc){
                printEdge(matrix, lr++, lc++, rr--, rc--);
            }
        }
    
        /**
         * 打印四条边：边界处理+四个while循环
         * @param matrix：矩阵
         * @param lr：左上角元素横坐标
         * @param lc：左上角元素纵坐标
         * @param rr：右下角元素横坐标
         * @param rc：右下角元素纵坐标
         */
        public void printEdge(int[][] matrix, int lr, int lc, int rr, int rc){
            if(lr == rr){
                // 如果 lr == rr ：说明只有一行数据，那只打印这一行数据就可以了
                for(int i = lc; i <= rc; i++){
                    System.out.print(matrix[lr][i] + " ");
                }
            }else if(lc == rc){
                // 如果 lc == rc ：说明只有一列数据，那只打印这一列数据就可以了
                for(int i = lr; i <= rr; i++){
                    System.out.print(matrix[lc][i] + " ");
                }
            }else{
                int curC = lc;
                int curR = lr;
                while (curC != rc){
                    // 打印上横线
                    System.out.print(matrix[lr][curC] + " ");
                    curC++;
                }
                while (curR != rr){
                    // 打印右竖线
                    System.out.print(matrix[curR][rc] + " ");
                    curR++;
                }
                while(curC != lc){
                    // 打印下横线
                    System.out.print(matrix[rr][curC] + " ");
                    curC--;
                }
                while(curR != lr){
                    // 打印左竖线
                    System.out.print(matrix[curR][lc] + " ");
                    curR--;
                }
            }
        }
    
        // 测试
        public static void main(String[] args){
            PrintMatrix pm = new PrintMatrix();
            int[][] matrix = {
       {1,2,3},{4,5,6},{7,8,9}};
            pm.printMatrix(matrix);
        }
    }

### 题目2：将一个正方形顺时针旋转90度 ###

*  思路：这题的思路和题目6很相似。**一定要画图出来看一看，找出规律就很好实现了。**
 *  **怎么在找到一个点后，通过这个点找到另外三个点，要注意边界条件。**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70][]

如上图所示：

>  *  13位置换到1位置、1位置换到4位置、4位置换到16位置、16位置换到13位置；
>  *  9位置换到2位置、2位置换到8位置、8位置换到15位置、15位置换到9位置；
>  *  5位置换到3位置、3位置换到13位置、12位置换到14位置、14位置换到5位置。

package com.offer.class3;
    
    /**
     * 旋转一个正方形：一定要将图画出来，找出来规律，就好写了
     */
    public class RotateMatrix {
    
        /**
         * 将一个正方形旋转90度
         * @param matrix
         */
        public int[][] rotateMatrix(int[][] matrix){
            if(matrix.length != matrix[0].length){
                throw new IllegalArgumentException("error : the input is error!");
            }
    
            int lr = 0;
            int lc = 0;
            int rr = matrix.length - 1;
            int rc = rr;
    
            while(lr < rr){
                rotateEdge(matrix, lr++, lc++, rr--, rc--);
            }
            return matrix;
        }
    
        /**
         * 一个正方形圈旋转90度
         * @param matrix：正方形
         * @param lr：左上角行号
         * @param lc：左上角列号
         * @param rr：右下角行号
         * @param rc：右下角列号
         */
        public void rotateEdge(int[][] matrix, int lr, int lc, int rr, int rc){
            int times = rc - lc;   // 旋转的次数 = 行数/列数 - 1
            int tmp = 0;
            // 互换四个点的位置,逆时针依次互换过来
            for(int i = 0; i != times; i++){
                tmp = matrix[lr][lc + i];
                matrix[lr][lc + i] = matrix[rr - i][lc];   // 上横线的位置元素换成左竖线的位置元素
                matrix[rr - i][lc] = matrix[rr][rc - i];   // 左竖线的位置元素换成下横线的位置元素
                matrix[rr][rc - i] = matrix[lr + i][rc];   // 下横线的位置元素换成右竖线的位置元素
                matrix[lr + i][rc] = tmp;                  // 右竖线的位置元素换成上横线的位置元素
            }
        }
    
        // 测试
        public static void main(String[] args){
            RotateMatrix rm = new RotateMatrix();
            int[][] matrix = new int[][]{
       {1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};
            int[][] res = rm.rotateMatrix(matrix);
            for(int i = 0; i < res.length; i++){
                for(int j = 0; j < res[0].length; j++){
                    System.out.print(res[i][j] + " ");
                }
                System.out.println();
            }
        }
    }

### 题目3：之字形打印矩阵 ###

*  【题目】 给定一个矩阵 matrix，按照“之”字形的方式打印这个矩阵，例如：

1  2  3  4  
    5  6  7  8  
    9  10 11 12
    “之”字形打印的结果为：1，2，5，9，6，3，4，7，10，11，8，12
    【要求】 额外空间复杂度为O(1)。

[![E4_B9_8B_E5_AD_97_E5_BD_A2_E6_89_93_E5_8D_B0_E7_9F_A9_E9_98_B5.png_raw_true][]][E4_B9_8B_E5_AD_97_E5_BD_A2_E6_89_93_E5_8D_B0_E7_9F_A9_E9_98_B5.png_raw_true 1]

*  【分析】：同样要从宏观来看，看成不断打印斜线，每打印了一条斜线就换方向来打印下一条斜线
    
     *  刚开始时A（row2，coll2）、B(row ,coll)位于（0,0）处，然后A往右走，走到尽头就往下面走，同时B往下走，走到尽头就往右走，当两者走到末尾右下角时所有的打印都结束了。

package com.offer.class3;
    
    /**
     * @author pengcheng
     * @date 2019-03-26 15:32
     * content：之字形打印一个矩阵
     */
    public class PrintZigMatrix {
    
        public void printZigMatrix(int[][] matrix){
            // 每次打印轨迹的两个端点：A(a,b) B(c,d)
            int a = 0, b = 0, c = 0, d = 0;
            // 矩阵右下角的坐标：(endRow,endCol)
            int endRow = matrix.length - 1;
            int endCol = matrix[0].length - 1;
    
            // 判断每次打印的方向，每打印一次就需要换向
            boolean direction = true;
    
            // A是先往右走，走到最右往下走；B是先往下走，走到最下开始往右走
            while (a <= endRow && b <= endCol){
                printSlash(matrix, a, b, c, d, direction);
                direction = !direction;  // 换向
                // A如果走到了最右边，则开始向下走，b必须要在a的下面，因为b值改变了会直接影响到a
                a = b >= endCol ? a + 1 : a;
                b = b < endCol ? b + 1 : b;
    
                // B如果走到了最下面，则开始向右走，c必须要在d的下面，因为c值改变了会直接影响到d
                d = c >= endRow ? d + 1 : d;
                c = c < endRow ? c + 1 : c;
            }
        }
    
        // 打印A和B两个点之间的轨迹
        public void printSlash(int[][] matrix, int a, int b, int c, int d, boolean direction){
            // direction为true时为从下往上打印，即 B --> A
            if(direction){
                for(; a <= c; c--, d++){
                    System.out.print(matrix[c][d] + " ");
                }
            }else{
                for(; a <= c; a++, b--){
                    System.out.print(matrix[a][b] + " ");
                }
            }
        }
    
        // 测试
        public static void main(String[] args){
            PrintZigMatrix pzm = new PrintZigMatrix();
            int[][] matrix = new int[][]{
       {1,2,3,4},{5,6,7,8},{9,10,11,12}};
            pzm.printZigMatrix(matrix);  // 1 2 5 9 6 3 4 7 10 11 8 12 
        }
    }

### 题目4：在一个行和列都有序的m行n列的矩阵中查找一个数是否存在 ###

*  要求时间复杂度为O(m+n)

**【分析】：从第一行的最后一个数开始查询，当前查询的数记作a(i,j)，因为是排好序的，所以：**

*  若 a < k，则a所在行左边的数都一定小于 k，所以 a 向下移动； 
 *  若 a > k，则a所在列的下方的数一定都大于 k，所以 a 向左移动;
 *  否则，a = k，返回 true;
 *  若查完了矩阵都没有返回，说明 k 不在矩阵中，返回 false。

package com.offer.class3;
    
    /**
     * @author pengcheng
     * @date 2019-03-26 16:52
     * content：在一个行和列都排好序的矩阵中查找一个数。要求时间复杂度为：O(n+m)
     */
    public class SearchInSortedMatrix {
    
        public boolean search(int[][] matrix, int k){
            int i = 0;
            int j = matrix[0].length - 1;
    
            // 从右上角开始搜索
            while(i < matrix.length && j > -1){
                if(matrix[i][j] < k){
                    // matrix[i][j] 如果小于 k ，则在matrix[i][j]下方找
                    i++;
                }else if(matrix[i][j] > k){
                    // matrix[i][j] 如果大于 k ，则在matrix[i][j]左边找
                    j--;
                }else{
                    return true;   // matrix[i][j] = k
                }
            }
            return false;
        }
    
        // 测试
        public static void main(String[] args){
            SearchInSortedMatrix search = new SearchInSortedMatrix();
            int[][] matrix = new int[][]{
       {0,1,2,5},{2,3,4,7},{4,4,4,8}};
            Boolean res = search.search(matrix, 8);
            System.out.print(res);
        }
    }

## ##

[https_blog.csdn.net_pcwl1206_article_details_85938437]: https://blog.csdn.net/pcwl1206/article/details/85938437
[20190326142136888.png]: /images/20220228/f800f1fa1eee4e91ac520b66a46dcd04.png
[https_blog.csdn.net_pcwl1206_article_details_85931023]: https://blog.csdn.net/pcwl1206/article/details/85931023
[20190326100648197.png]: /images/20220228/d709aeec76d94c9a8dabfd994d9e7751.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70]: /images/20220228/75711b96a24c434d8dd8298ce29213eb.png
[E4_B9_8B_E5_AD_97_E5_BD_A2_E6_89_93_E5_8D_B0_E7_9F_A9_E9_98_B5.png_raw_true]: https://github.com/zhaojing5340126/interview/raw/master/picture/%E4%B9%8B%E5%AD%97%E5%BD%A2%E6%89%93%E5%8D%B0%E7%9F%A9%E9%98%B5.png?raw=true
[E4_B9_8B_E5_AD_97_E5_BD_A2_E6_89_93_E5_8D_B0_E7_9F_A9_E9_98_B5.png_raw_true 1]: https://github.com/zhaojing5340126/interview/blob/master/picture/%E4%B9%8B%E5%AD%97%E5%BD%A2%E6%89%93%E5%8D%B0%E7%9F%A9%E9%98%B5.png?raw=true