一、矩阵题目练习

（1）转圈打印矩阵

• 题目：给定一个整型矩阵matrix,请按照转圈的方式打印它

• 例如：
  1    2    3    4
  5    6    7    8
  9   10  11  12
  13 14  15  16
  打印结果为：1，2，3，4，8，12，16，15，14，13，9，5，6，7，11，10

• 要求：额外空间复杂度为O(1)

• 解题思路：获取矩阵左上角点的坐标和右下角的点的坐标，通过这两个点首先实现最为外面一圈的打印，首先左上角的点的坐标，横坐标一直加加，直到等于右下角横坐标，横坐标不在改变，纵坐标开始加加，直到等于右下角纵坐标，然后纵坐标不变，横坐标开始减减直到等于左上角的横坐标，横坐标不再改变，纵坐标开始减减直到等与左上角的纵坐标。这用一圈就打印完了，只要把左上角的横纵坐标加一和右下角的横纵坐标减一继续打印一圈。重复上面直至打印结束。

代码示例：

public class ZhuanQuanPrint {
    public static void zhuanquanPrint(int[][] martix) {
        int row1=0;
        int col1=0;
        int row2=martix.length-1;
        int col2=martix[0].length-1;
        while(row1<=row2&&col1<=col2) {
        print(martix, row1++, col1++, row2--, col2--);
        }
        
    }
    public static void print(int[][] martix,int row1,int col1,int row2,int col2) {
        int row=row1;
        int col=col1;
        if(row1==row2&&col1==col2) {
            System.out.print(martix[row1][col1]+" ");
        }else if(row1==row2&&col1!=col2) {
            while(col1<=col2) {
                System.out.print(martix[row1][col1++]+" ");
            }
        }else if(row1!=row2&&col1==col2) {
            while(row1<=row2) {
                System.out.print(martix[row1++][col1]+" ");
            }
        }else {
        while(col!=col2) {
            System.out.print(martix[row][col++]+" ");
        }
        while(row!=row2) {
            System.out.print(martix[row++][col]+" ");
        }
        while(col!=col1) {
            System.out.print(martix[row][col--]+" ");
        }
        while(row!=row1) {
            System.out.print(martix[row--][col]+" ");
        }
        }
        
    }
    public static void main(String[] args) {
        int[][] martix= {{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};
        zhuanquanPrint(martix);
    }

}

（2）之字形打印矩阵

• 题目：给定一个矩阵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)

• 解题思路：设立两个指针都指向零零位置一个指针只往下走，另一个只往
  右走，当往下走的指针碰壁后往右走，往右走的指针碰壁后开始往下走，每次只需要打印两点之间对角线的数就可以，设置一个布尔类型的变量，为true时正向打印对角线，为false时反向打印对角线

• 代码示例：

public class ZhiPrint {
public static void zhiPrint(int[][] martix) {
    boolean flag=true;
    int col1=0;
    int row1=0;
    int col2=0;
    int row2=0;
    while(col2<=martix[0].length) {
        print(martix,col1,row1,col2,row2,flag);
        //此处要注意顺序，否则就会产生错误，我注释的是错误的
        //因为第一行的col1=col1+1影响了第二行的（col1==martix[0].length-1）判断
        row1=col1==martix[0].length-1?row1+1:row1;//col1=col1==martix[0].length-1?col1:col1+1;
        col1=col1==martix[0].length-1?col1:col1+1;//row1=col1==martix[0].length-1?row1+1:row1;
        col2=row2==martix.length-1?col2+1:col2;   //row2=row2==martix.length-1?row2:row2+1;
        row2=row2==martix.length-1?row2:row2+1;   //col2=row2==martix.length-1?col2+1:col2;
        
        flag=!flag;
    }
}
public static void print(int[][] martix,int col1,int row1,int col2,int row2,boolean flag) {
    if(flag) {
        while(col2<=col1) {
            System.out.print(martix[row2--][col2++]+" ");
        }
    }else {
        while(row1<=row2) {
        System.out.print(martix[row1++][col1--]+" ");
        }
    }
}
public static void main(String[] args) {
    int[][] martix={{1,2,3,4},{5,6,7,8},{9,10,11,12}};
    zhiPrint(martix);
}
}

(3)在行列都排好的矩阵中找数

• 题目：给定一个有N*M的整型矩阵matrix和一个整数K,matrix的每一行和每一列都是排好序的，实现一个函数，判断K是否在matrix中。
• 要求：时间复杂度为O(N+M),额外空间复杂度为O(1)
• 解题思路：此题有两个起始点去找，一个是左下角的点，另一个是右下角的点。但是思路是一样的，我只说从右上角开始找，首先判断右上角这个点是否等于目标数，如等于返回true，若不等判断比目标数大还是小如果小，往下移一个点，如果大往左移一个点。重复以上操作左边界越界或者下边界越界
• 代码示例：

public class FindNumber {
public static boolean find(int[][] martix,int k){
    int row=0;
    int col=martix[0].length-1;
    while(row<martix.length&&col>=0) {
        if(martix[row][col]==k) {
            return true;
        }else if(martix[row][col]<k) {
            row++;
        }else {
            col--;
        }
    }
    return false;
}
public static void main(String[] args) {
    int[][] martix= {{0,1,2,5},{2,3,4,7},{4,4,4,8},{5,7,7,9}};
    System.out.println(find(martix,6));
}
}

二、链表练习

（1）打印两个有序的链表的公共部分

• 题目：给定两个有序链表的头指针head1和head2，打印两个链表的公共部分
• 解题思路：采用外排的方式，谁小谁往后走，遇到相同的打印然后同时往后走一个节点
• 代码示例：

class Node{
    Node next=null;
    int data;
    public Node(int data) {
        this.data=data;
    }
    
}
public class SamePart {
public static void samePart(Node head1,Node head2) {
    Node index1=head1;
    Node index2=head2;
    while(index1!=null&&index2!=null) {
        if(index1.data<index2.data) {
            index1=index1.next;
        }else if(index1.data>index2.data) {
            index2=index2.next;
        }else {
            System.out.print(index1.data+" ");
            index1=index1.next;
            index2=index2.next;
        }
    }
}
public static void main(String[] args) {
    Node head1=new Node(1);
    Node index=head1;
    for(int i=2;i<10;i++) {
        index.next=new Node(i);
        index=index.next;
    }
    Node head2=new Node(1);
    Node index2=head2;
    for(int i=2;i<10;i=i+2) {
        index2.next=new Node(i);
        index2=index2.next;
    }
    samePart(head1,head2);
}
}

(2)判断一个链表是否为回文结构

• 题目：给定一个链表的头节点head,请判断该链表 是否为回文结构

• 例如：
  1->2->1返回true
  1->2->2->1返回true
  1->2->3返回false

• 进阶：如果链表长度为N,时间复杂度达到O（n）,额外空间复杂达到O(1)

• 普通解题思路：拿一个栈把每个节点压进去，然后出栈的时候和原来的链表比，如果一样则为回文结构，还有一个进阶一点的办法，设置一个快指针一次走一步，设置一个慢指针一次走两步，当快指针走到终点时慢指针刚好走到中点，然后把中点位置后面的压进栈里，然后出栈的时候比一下
  普通思路代码示例：

class Node1{
    Node1 next=null;
    int data;
    public Node1(int data) {
        this.data=data;
    }
}
public class HuiWenSimple {
public static boolean huiWen(Node1 head) {
    Node1 index=head;
    Stack<Node1> stack=new Stack<>();
    boolean ishave=true;
    while(index!=null) {
        stack.push(index);
        index=index.next;
    }
    index=head;
    while(index!=null) {
        ishave=(ishave&index.data==stack.pop().data);
        index=index.next;
    }
    return ishave;
}
public static void main(String[] args) {
    Node1 head=new Node1(1);
    head.next=new Node1(2);
    head.next.next=new Node1(1);
    System.out.print(huiWen(head));
}
}

• 进阶解题思路：设置快慢指针，依旧快指针走两步，慢指针走一步，找到中点节点，把节点后面的位置逆序过来然后比较，比较结束后再把逆序的部分转回去。
• 进阶代码示例：(特别绕，有难度)

class Node2{
    Node2 next=null;
    int data;
    public Node2(int data) {
        this.data=data;
    }
}
public class HuiWenHard {
public static boolean huiWen(Node2 head) {
    Node2 fast=head;
    Node2 slow=head;
    boolean ishave=true;
    while(fast!=null&&fast.next!=null&&fast.next.next!=null) {
        fast=fast.next.next;
        slow=slow.next;
    }
    Node2 index=slow.next;
    //Node2 index2=slow.next;
    slow.next=null;
    Node2 index2=null;
    while(index!=null) {
        index2=index.next;
        index.next=slow;
        slow=index;
        index=index2;   
    }
    index2=slow;
    Node2 index3=head;
    while(slow!=null&&index3!=null) {
        ishave=(ishave&&slow.data==index3.data);
        index3=index3.next;
        slow=slow.next;
    }
    slow=index2.next;
    index2.next=null;
    while(slow!=null){
        index3=slow.next;
        slow.next=index2;
        index2=slow;
        slow=index3;    
    }
    return ishave;
    
}
public static void main(String[] args) {
    Node2 head=new Node2(1);
    head.next=new Node2(2);                  
    head.next.next=new Node2(2);
    head.next.next.next=new Node2(1);
    System.out.println(huiWen(head));
    while(head!=null) {
        System.out.print(head.data+" ");
        head=head.next;
    }
}
}

（3）将单向链表按某值划分成左边小，中间相等，右边大的形式

题目：给定一个单向链表的头节点head，节点的值的类型是整型，在给定一个整数pivot。实现一个调整链表的函数，将链表调整为左部分值都是小于pivot的节点，中间部分值都是等于pivot，右边的值都是大于pivot

解题思路1（简单的）：将链表的所有节点放进数组里，然后采用数组快速排序的基本一步就可以，如不知道快排请看算法入门（一)

代码示例：