栈、队列、矩阵、链表问题（二）
2018-12-18 本文已影响9人
管弦_
目录
- “之”字形打印
- 在行列都排好序的矩阵中找数
- 打印两个有序链表的公共部分
- 判断一个链表是否为回文结构
- 将单向链表按某值划分成左边小、中间相等、右边大的形式
- 复制含有随机指针节点的链表
- 两个单链表相交的一系列问题
“之”字形打印
【题目】 给定一个矩阵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)。
思路：如果一直随着“之”字轨迹计算下标，那算法就非常繁琐复杂，我们需要找到更简洁的方式。这里我们可以引入两个辅助坐标a，b。a向矩阵的右侧移动，到最右侧时就向下移动；b向下移动，到最底层时就向右移动。每次a和b只移动一步，并且交叉打印a和b的连接线经过的所有元素，直到a和b在最右下角重合。
public static void printMatrixZigZag(int[][] matrix) {
int ay = 0;
int ax = 0;
int by = 0;
int bx = 0;
int endY = matrix.length - 1;
int endX = matrix[0].length - 1;
boolean fromUp = false;
while (ay != endY + 1) {
printLevel(matrix, ay, ax, by, bx, fromUp);
ay = ax == endX ? ay + 1 : ay;
ax = ax == endX ? ax : ax + 1;
bx = by == endY ? bx + 1 : bx;
by = by == endY ? by : by + 1;
fromUp = !fromUp;
}
System.out.println();
}
public static void printLevel(int[][] m, int ay, int ax, int by, int bx, boolean f) {
if (f) {
while (ay != by + 1) {
System.out.print(m[ay++][ax--] + " ");
}
} else {
while (by != ay - 1) {
System.out.print(m[by--][bx++] + " ");
}
}
}
在行列都排好序的矩阵中找数
【题目】 给定一个有N*M的整型矩阵matrix和一个整数K，matrix的每一行和每一列都是排好序的。实现一个函数，判断K是否在matrix中。例如： 0 1 2 5 2 3 4 7 4 4 4 8 5 7 7 9。如果K为7，返回true；如果K为6，返回false。
【要求】 时间复杂度为O(N+M)，额外空间复杂度为O(1)
思路：应该好好利用行列都排好序的这个特性。我们从第一行的最后一个数开始判断，如果该数大于k，那么继续在该行中找，如果该数小于k，那么换到下一行。
public static boolean isContains(int[][] matrix, int k){
int row = 0;
int col = matrix[0].length - 1;
while (row < matrix.length && col > -1){
if(matrix[row][col] == k){
return true;
}else if(matrix[row][col] > k){
col--;
}else{
row++;
}
}
return false;
}
打印两个有序链表的公共部分
【题目】 给定两个有序链表的头指针head1和head2，打印两个链表的公共部分。
思路：因为是有序链表，所有两个链表的头开始如下判断：
- 如果head1的值小于head2,则head1向下移动
- 如果head1的值大于head2,则head2向下移动
- 如果head1等于haed2，则打印这个值，然后head1和head2都向下移动
public static class Node {
public int value;
public Node next;
public Node(int data) {
this.value = data;
}
}
public static void printCommonPart(Node head1, Node head2) {
while (head1 != null && head2 != null){
if(head1.value > head2.value){
head2 = head2.next;
} else if(head1.value < head2.value){
head1 = head1.next;
} else {
System.out.print(head1.value);
head1 = head1.next;
head2 = head2.next;
}
}
}
判断一个链表是否为回文结构
【题目】 给定一个链表的头节点head，请判断该链表是否为回文结构。 例如： 1->2->1，返回true。 1->2->2->1，返回true。15->6->15，返回true。 1->2->3，返回false。
思路：我们可以使用一个栈结构将链表对象压入其中，然后每弹出一个元素与链表的next元素比较。
public static boolean isPalindrome1(Node head) {
Stack<Node> stack = new Stack<>();
Node cur = head;
while (cur != null){
stack.push(cur);
cur = cur.next;
}
while (head != null){
if(head.value == stack.pop().value){
return true;
}
}
return false;
}
进阶： 如果链表长度为N，时间复杂度达到O(N)，额外空间复杂度达到O(1)
思路：由于额外空间复杂度为O(1)，那么不能再使用栈的方式。
- 我们可以使用快慢指针法，设置一个快指针和一个慢指针，慢指针一次走一步，快指针一次走两步，当快指针指向null，说明慢指针走到了链表中间位置。
- 反转中间链表后面的指针。从头尾向中间扫描，对比每个元素是否相等，如果都相等，则是回文数，否则不是回文数。
// need O(1) extra space
public static boolean isPalindrome3(Node head) {
if (head == null || head.next == null) {
return true;
}
Node n1 = head;
Node n2 = head;
while (n2.next != null && n2.next.next != null) { // find mid node
n1 = n1.next; // n1 -> mid
n2 = n2.next.next; // n2 -> end
}
n2 = n1.next; // n2 -> right part first node
n1.next = null; // mid.next -> null
Node n3 = null;
while (n2 != null) { // right part convert
n3 = n2.next; // n3 -> save next node
n2.next = n1; // next of right node convert
n1 = n2; // n1 move
n2 = n3; // n2 move
}
n3 = n1; // n3 -> save last node
n2 = head;// n2 -> left first node
boolean res = true;
while (n1 != null && n2 != null) { // check palindrome
if (n1.value != n2.value) {
res = false;
break;
}
n1 = n1.next; // left to mid
n2 = n2.next; // right to mid
}
n1 = n3.next;
n3.next = null;
while (n1 != null) { // recover list
n2 = n1.next;
n1.next = n3;
n3 = n1;
n1 = n2;
}
return res;
}
将单向链表按某值划分成左边小、中间相等、右边大的形式
【题目】 给定一个单向链表的头节点head，节点的值类型是整型，再给定一个整数pivot。实现一个调整链表的函数，将链表调整为左部分都是值小于pivot的节点，中间部分都是值等于pivot的节点，右部分都是值大于pivot的节点。
思路：可以创建一个辅助数组，将链表的所有节点全部填入数组中，按需求划分好以后在拼装回链表。
public static class Node {
public int value;
public Node next;
public Node(int data) {
this.value = data;
}
}
public static Node listPartition1(Node head, int pivot) {
if (head == null) {
return head;
}
Node cur = head;
int i = 0;
while (cur.next != null) {
i++;
cur = cur.next;
}
Node[] nodeArr = new Node[i];
i = 0;
cur = head;
for (i = 0; i != nodeArr.length; i++) {
nodeArr[i] = cur;
cur = cur.next;
}
arrPartition(nodeArr, pivot);
for (i = 1; i != nodeArr.length; i++) {
nodeArr[i - 1].next = nodeArr[i];
}
nodeArr[i - 1].next = null;
return nodeArr[0];
}
private static void arrPartition(Node[] nodeArr, int pivot) {
int small = -1;
int big = nodeArr.length;
int index = 0;
while (index != big) {
if (nodeArr[index].value < pivot) {
swap(nodeArr, ++small, index++);
} else if (nodeArr[index].value == pivot) {
index++;
} else {
swap(nodeArr, --big, index);
}
}
}
public static void swap(Node[] nodeArr, int a, int b) {
Node tmp = nodeArr[a];
nodeArr[a] = nodeArr[b];
nodeArr[b] = tmp;
}
进阶：在原问题的要求之上再增加如下两个要求。
- 在左、中、右三个部分的内部也做顺序要求，要求每部分里的节点从左到右的顺序与原链表中节点的先后次序一致。
- 如果链表长度为N，时间复杂度请达到O(N)，额外空间复杂度请达到O(1)。
思路：将链表分为3段：小于、等于、大于部分。每一部分组成一个链表，并且分别有两个指针指向头部和尾部，遍历链表时按需求将每个节点分别接入各自的链表中，完成以后再组成一个完整链表，这样就保证了链表结构的稳定性。
public static Node listPartition2(Node head, int pivot) {
Node sH = null; // small head
Node sT = null; // small tail
Node eH = null; // equal head
Node eT = null; // equal tail
Node bH = null; // big head
Node bT = null; // big tail
Node next = null; // save next node
// every node distributed to three lists
while (head != null) {
next = head.next;
head.next = null;
if (head.value < pivot) {
if (sH == null) {
sH = head;
sT = head;
} else {
sT.next = head;
sT = head;
}
} else if (head.value == pivot) {
if (eH == null) {
eH = head;
eT = head;
} else {
eT.next = head;
eT = head;
}
} else {
if (bH == null) {
bH = head;
bT = head;
} else {
bT.next = head;
bT = head;
}
}
head = next;
}
// small and equal reconnect
if (sT != null) {
sT.next = eH;
eT = eT == null ? sT : eT;
}
// all reconnect
if (eT != null) {
eT.next = bH;
}
return sH != null ? sH : eH != null ? eH : bH;
}
复制含有随机指针节点的链表
思路：使用HashMap结构，key为原链表的节点，value为复制的节点。将源节点对应的复制节点的每一个指针都指向原节点目标节点对应复制节点。
public static class Node {
public int value;
public Node next;
public Node rand;
public Node(int data) {
this.value = data;
}
}
public static Node copyListWithRand1(Node head) {
HashMap<Node, Node> map = new HashMap<>();
Node cur = head;
while (cur != null){
map.put(cur, new Node(cur.value));
cur = cur.next;
}
cur = head;
while (cur != null){
map.get(cur).next = map.get(cur.next);
map.get(cur).rand = map.get(cur.rand);
cur = cur.next;
}
return map.get(head);
}
进阶：不使用额外的数据结构，只用有限几个变量，且在时间复杂度为O(N)内完成原问题要实现的函数。
思路：
- 将每一个原节点next指针指向它的复制节点，复制节点next指针再指向下一个原节点。
- 再将复制节点的rand指针指向原节点rand指针指向的节点的复制节点。
- 最后将复制节点next指针指向下一个复制节点。
public static Node copyListWithRand2(Node head) {
if (head == null) {
return null;
}
Node cur = head;
Node next = null;
// copy node and link to every node
while (cur != null) {
next = cur.next;
cur.next = new Node(cur.value);
cur.next.next = next;
cur = next;
}
cur = head;
Node curCopy = null;
// set copy node rand
while (cur != null) {
next = cur.next.next;
curCopy = cur.next;
curCopy.rand = cur.rand != null ? cur.rand.next : null;
cur = next;
}
Node res = head.next;
cur = head;
// split
while (cur != null) {
next = cur.next.next;
curCopy = cur.next;
cur.next = next;
curCopy.next = next != null ? next.next : null;
cur = next;
}
return res;
}
两个单链表相交的一系列问题
【题目】 在本题中，单链表可能有环，也可能无环。给定两个单链表的头节点head1和head2，这两个链表可能相交，也可能不相交。请实现一个函数，如果两个链表相交，请返回相交的第一个节点；如果不相交，返回null即可。要求：如果链表1的长度为N，链表2的长度为M，时间复杂度请达到O(N+M)，额外空间复杂度请达到O(1)。
思路：先判断两个链表是否有环，一个有环一个无环那么必定不想交；两个都无环或两个都有环，则需要分开处理。
判断链表是否有环，需要使用快指针、慢指针，快指针走两步，慢指针走一步，当快指针和慢指针重合，快指针指向头部，并且改为一次走一步。下一次快慢指针重合时，就是入环节点。
public static Node getIntersectNode(Node head1, Node head2) {
if (head1 == null || head2 == null) {
return null;
}
Node loop1 = getLoopNode(head1);
Node loop2 = getLoopNode(head2);
if (loop1 == null && loop2 == null) {
//两个都无环
return noLoop(head1, head2);
}
if (loop1 != null && loop2 != null) {
//两个都有环
return bothLoop(head1, loop1, head2, loop2);
}
return null;
}
//判断是否有环
public static Node getLoopNode(Node head) {
if (head == null || head.next == null || head.next.next == null) {
return null;
}
Node n1 = head.next; // n1 -> slow
Node n2 = head.next.next; // n2 -> fast
while (n1 != n2) {
if (n2.next == null || n2.next.next == null) {
return null;
}
n2 = n2.next.next;
n1 = n1.next;
}
n2 = head; // n2 -> walk again from head
while (n1 != n2) {
n1 = n1.next;
n2 = n2.next;
}
return n1;
}
若两个都是无环链表，如果两个链表尾部都没有重合，则必定不相交；如果相交，那么先得到两个链表的长度差值n，然后长链表先走n步，再同步往下走，直到两个链表的节点重合，即相交交点。
public static Node noLoop(Node head1, Node head2) {
if (head1 == null || head2 == null) {
return null;
}
Node cur1 = head1;
Node cur2 = head2;
int n = 0;
while (cur1.next != null) {
n++;
cur1 = cur1.next;
}
while (cur2.next != null) {
n--;
cur2 = cur2.next;
}
if (cur1 != cur2) {
return null;
}
cur1 = n > 0 ? head1 : head2;
cur2 = cur1 == head1 ? head2 : head1;
n = Math.abs(n);
while (n != 0) {
n--;
cur1 = cur1.next;
}
while (cur1 != cur2) {
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
}
若两个都是有环链表，先判断两个链表的入环节点是否是一个节点，是一个节点则说明两个链表共享一个环，必定相交，只需按无环链表的方式得到交点即可。如果入环节点不是一个节点，要么不想交，要么相交但入环点不在一个位置。此时只需在第一个链表的入环点向下寻找，如果找到第二个入环点，即相交；找不到就不想交。
public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
Node cur1 = null;
Node cur2 = null;
if (loop1 == loop2) {
cur1 = head1;
cur2 = head2;
int n = 0;
while (cur1 != loop1) {
n++;
cur1 = cur1.next;
}
while (cur2 != loop2) {
n--;
cur2 = cur2.next;
}
cur1 = n > 0 ? head1 : head2;
cur2 = cur1 == head1 ? head2 : head1;
n = Math.abs(n);
while (n != 0) {
n--;
cur1 = cur1.next;
}
while (cur1 != cur2) {
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
} else {
cur1 = loop1.next;
while (cur1 != loop1) {
if (cur1 == loop2) {
return loop1;
}
cur1 = cur1.next;
}
return null;
}
}
参考资料：牛客网左程云初级算法教程
