一、矩阵

54.螺旋矩阵(循环不变量)

一个矩阵，循环遍历出来，就得按照顺序去遍历，然后插到我们定义的矩阵里面去

class Solution {public int[][] generateMatrix(int n) {int[][] nums = new int[n][n];//定义一个矩阵int startX = 0, startY = 0;  // 每一圈的起始点int offset = 1;int count = 1;  // 矩阵中需要填写的数字int loop = 1; // 记录当前的圈数int i, j; // j 代表列, i 代表行;while (loop <= n / 2) {// 顶部// 左闭右开，所以判断循环结束时， j 不能等于 n - offsetfor (j = startY; j < n - offset; j++) {nums[startX][j] = count++;}// 右列// 左闭右开，所以判断循环结束时， i 不能等于 n - offsetfor (i = startX; i < n - offset; i++) {nums[i][j] = count++;}// 底部// 左闭右开，所以判断循环结束时， j != startYfor (; j > startY; j--) {nums[i][j] = count++;}// 左列// 左闭右开，所以判断循环结束时， i != startXfor (; i > startX; i--) {nums[i][j] = count++;}startX++;startY++;offset++;loop++;}if (n % 2 == 1) { // n 为奇数时，单独处理矩阵中心的值nums[startX][startY] = count;}return nums;}
}

二、链表

1 移除链表元素

1.1 原链表删除元素：

/*** 不添加虚拟节点and pre Node方式* 时间复杂度 O(n)* 空间复杂度 O(1)* @param head* @param val* @return*/
public ListNode removeElements(ListNode head, int val) {while(head!=null && head.val==val){//head!=null用于防止空指针错误，如果头节点就等于val的话直接让头节点指向下一位。head = head.next;}ListNode curr = head;//把头节点的位置拿到while(curr!=null){//防止空指针while(curr.next!=null && curr.next.val == val){//头指针的下一个也不为null，下一个为val，那么我们的的next就要等于next.next了curr.next = curr.next.next;}curr = curr.next;//把等于的值的curr返回。}return head;
}

1.2 虚拟头节点（！！！）

/*** 添加虚节点方式* 时间复杂度 O(n)* 空间复杂度 O(1)* @param head* @param val* @return*/
public ListNode removeElements(ListNode head, int val) {if (head == null) {return head;}// 因为删除可能涉及到头节点，所以设置dummy节点，统一操作ListNode dummy = new ListNode(-1, head);ListNode pre = dummy;ListNode cur = head;while (cur != null) {if (cur.val == val) {pre.next = cur.next;} else {pre = cur;}cur = cur.next;}return dummy.next;
}

2. 设计链表

//单链表
class ListNode {int val;ListNode next;ListNode(){}ListNode(int val) {this.val=val;}
}
class MyLinkedList {//size存储链表元素的个数int size;//虚拟头结点ListNode head;//初始化链表public MyLinkedList() {size = 0;head = new ListNode(0);}//获取第index个节点的数值，注意index是从0开始的，第0个节点就是头结点public int get(int index) {//如果index非法，返回-1if (index < 0 || index >= size) {return -1;}ListNode currentNode = head;//包含一个虚拟头节点，所以查找第 index+1 个节点for (int i = 0; i <= index; i++) {currentNode = currentNode.next;}return currentNode.val;}//在链表最前面插入一个节点，等价于在第0个元素前添加public void addAtHead(int val) {addAtIndex(0, val);}//在链表的最后插入一个节点，等价于在(末尾+1)个元素前添加public void addAtTail(int val) {addAtIndex(size, val);}// 在第 index 个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。// 如果 index 等于链表的长度，则说明是新插入的节点为链表的尾结点// 如果 index 大于链表的长度，则返回空public void addAtIndex(int index, int val) {if (index > size) {return;}if (index < 0) {index = 0;}size++;//找到要插入节点的前驱ListNode pred = head;for (int i = 0; i < index; i++) {pred = pred.next;}ListNode toAdd = new ListNode(val);toAdd.next = pred.next;pred.next = toAdd;}//删除第index个节点public void deleteAtIndex(int index) {if (index < 0 || index >= size) {return;}size--;if (index == 0) {head = head.next;return;}ListNode pred = head;for (int i = 0; i < index ; i++) {pred = pred.next;}pred.next = pred.next.next;}
}//双链表
class ListNode{int val;ListNode next,prev;ListNode() {};ListNode(int val){this.val = val;}
}class MyLinkedList {  //记录链表中元素的数量int size;//记录链表的虚拟头结点和尾结点ListNode head,tail;public MyLinkedList() {//初始化操作this.size = 0;this.head = new ListNode(0);this.tail = new ListNode(0);//这一步非常关键，否则在加入头结点的操作中会出现null.next的错误！！！head.next=tail;tail.prev=head;}public int get(int index) {//判断index是否有效if(index<0 || index>=size){return -1;}ListNode cur = this.head;//判断是哪一边遍历时间更短if(index >= size / 2){//tail开始cur = tail;for(int i=0; i< size-index; i++){cur = cur.prev;}}else{for(int i=0; i<= index; i++){cur = cur.next; }}return cur.val;}public void addAtHead(int val) {//等价于在第0个元素前添加addAtIndex(0,val);}public void addAtTail(int val) {//等价于在最后一个元素(null)前添加addAtIndex(size,val);}public void addAtIndex(int index, int val) {//index大于链表长度if(index>size){return;}//index小于0if(index<0){index = 0;}size++;//找到前驱ListNode pre = this.head;for(int i=0; i<index; i++){pre = pre.next;}//新建结点ListNode newNode = new ListNode(val);newNode.next = pre.next;pre.next.prev = newNode;newNode.prev = pre;pre.next = newNode;}public void deleteAtIndex(int index) {//判断索引是否有效if(index<0 || index>=size){return;}//删除操作size--;ListNode pre = this.head;for(int i=0; i<index; i++){pre = pre.next;}pre.next.next.prev = pre;pre.next = pre.next.next;}
}

206. 反转链表(双向指针和递归)

双指针

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

class Solution {public ListNode reverseList(ListNode head) {ListNode cur=head;ListNode prev=null;ListNode temp=null;while(cur != null){temp=cur.next;//上面这俩位置是把拿到的值拼凑到一起cur.next=prev;prev=cur;//下面这俩位置，是用来去拿数的cur=temp;}return prev;}
}

递归

// 递归 
class Solution {public ListNode reverseList(ListNode head) {return reverse(null, head);}private ListNode reverse(ListNode prev, ListNode cur) {if (cur == null) {return prev;}ListNode temp = null;temp = cur.next;// 先保存下一个节点cur.next = prev;// 反转// 更新prev、cur位置// prev = cur;// cur = temp;return reverse(cur, temp);}
}

交换链表中的元素

虚拟头节点法

class Solution {public ListNode swapPairs(ListNode head) {ListNode dumyhead = new ListNode(-1); // 设置一个虚拟头结点dumyhead.next = head; // 将虚拟头结点指向head，这样方便后面做删除操作ListNode cur = dumyhead;ListNode temp; // 临时节点，保存两个节点后面的节点ListNode firstnode; // 临时节点，保存两个节点之中的第一个节点ListNode secondnode; // 临时节点，保存两个节点之中的第二个节点while (cur.next != null && cur.next.next != null) {temp = cur.next.next.next;firstnode = cur.next;secondnode = cur.next.next;cur.next = secondnode;       // 步骤一secondnode.next = firstnode; // 步骤二firstnode.next = temp;      // 步骤三cur = firstnode; // cur移动，准备下一轮交换}return dumyhead.next;  }
}

递归法

// 递归版本
class Solution {public ListNode swapPairs(ListNode head) {// base case 退出提交if(head == null || head.next == null) return head;// 获取当前节点的下一个节点ListNode next = head.next;// 进行递归ListNode newNode = swapPairs(next.next);// 这里进行交换next.next = head;head.next = newNode;return next;}
} 

删除链表的倒数第N个节点

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {//新建一个虚拟头节点指向headListNode dummyNode = new ListNode(0);dummyNode.next = head;//快慢指针指向虚拟头节点ListNode fastIndex = dummyNode;ListNode slowIndex = dummyNode;// 只要快慢指针相差 n 个结点即可for (int i = 0; i <= n; i++) {fastIndex = fastIndex.next;}while (fastIndex != null) {fastIndex = fastIndex.next;slowIndex = slowIndex.next;}// 此时 slowIndex 的位置就是待删除元素的前一个位置。// 具体情况可自己画一个链表长度为 3 的图来模拟代码来理解// 检查 slowIndex.next 是否为 null，以避免空指针异常if (slowIndex.next != null) {slowIndex.next = slowIndex.next.next;}return dummyNode.next;}
}

142. 环形链表 II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

 ListNode slow = head;ListNode fast = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast) {// 有环ListNode index1 = fast;ListNode index2 = head;// 两个指针，从头结点和相遇结点，各走一步，直到相遇，相遇点即为环入口while (index1 != index2) {index1 = index1.next;index2 = index2.next;}return index1;}}return null;}}

链表相交（学习思路）

(版本一)先行移动长链表实现同步移动
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode curA = headA;ListNode curB = headB;int lenA = 0, lenB = 0;while (curA != null) { // 求链表A的长度lenA++;curA = curA.next;}while (curB != null) { // 求链表B的长度lenB++;curB = curB.next;}curA = headA;curB = headB;// 让curA为最长链表的头，lenA为其长度if (lenB > lenA) {//1. swap (lenA, lenB);int tmpLen = lenA;lenA = lenB;lenB = tmpLen;//2. swap (curA, curB);ListNode tmpNode = curA;curA = curB;curB = tmpNode;}// 求长度差int gap = lenA - lenB;// 让curA和curB在同一起点上（末尾位置对齐）while (gap-- > 0) {curA = curA.next;}// 遍历curA 和 curB，遇到相同则直接返回while (curA != null) {if (curA == curB) {return curA;}curA = curA.next;curB = curB.next;}return null;}}(版本二) 合并链表实现同步移动
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {// p1 指向 A 链表头结点，p2 指向 B 链表头结点ListNode p1 = headA, p2 = headB;while (p1 != p2) {// p1 走一步，如果走到 A 链表末尾，转到 B 链表if (p1 == null) p1 = headB;else            p1 = p1.next;// p2 走一步，如果走到 B 链表末尾，转到 A 链表if (p2 == null) p2 = headA;else            p2 = p2.next;}return p1;}
}