牛客网视频总结4（矩阵、链表）
目录
矩阵
转圈打印矩阵
题目：按照1.2.3.4.8.12.16.15.14.13.9.5.6.7.11.10打印矩阵
- 先算外层，左上角给(a,b)，右下角给(c,d)，打印一圈
- 然后(a++,b++)为左上角，右下角为(c–,d–)，再打印一圈
- 存在两种特殊情况， ( a = = c ) (a==c) (a==c)表示同一行， ( b = = d ) (b==d) (b==d)表示同一列，需要单独考虑
- 如果左上行/列大于右下行/列，结束
方形矩阵顺时针旋转90°（不允许辅助数组）
答：先换外圈，再换里圈
- 先换1，4，16，13；再换2，8，15，9，再换3，12，14，5
- 对应找相应位置抠边界就行
- 左上>=右下停止
之字形打印矩阵
答：
- 设两个指针，A向右走，撞到了向下走；B向下走，撞到了向右走
- 再设计一个Boolean类型变量，代表左下到右上还是右上到左下
在行列都有序的矩阵中找数
要求时间复杂度
O
(
M
+
N
)
O(M+N)
O(M+N)，MN分别代表数组行列长度，额外空间复杂度
O
(
1
)
O(1)
O(1)
答：从右上出发，如果cur>target，则往左走；如果cur<target，则往下走
链表
打印链表公共部分
类似外排
链表反向
- 赋值n2=当前头部.next
- 当前指针.next指向null
- while: n3=n2.next，n2.next=当前指针，当前指针=n2，n2=n3
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
cur, pre = head, None
while cur:
tmp = cur.next # 暂存后继节点 cur.next
cur.next = pre # 修改 next 引用指向
pre = cur # pre 暂存 cur
cur = tmp # cur 访问下一节点
return pre。
判断链表是否为回文结构
第一种方法空间复杂度
O
(
N
)
O(N)
O(N)：所有节点都放到栈里去，弹出的顺序就是逆序，和原链表进行比对
第二种方法空间复杂度
O
(
1
)
O(1)
O(1)：快指针走2步，慢指针走1步，慢指针走到了中点位置，把中间后半部分给反序，从左右两个顶点分别开始比对。
链表的荷兰国旗问题
方法一：生成一个数组结构，数组装的是节点类型，根据荷兰问题重排
进阶问题：左中右三部分的内部做顺序要求，90451，target=3，调整为01945，同时要求时间复杂度
O
(
N
)
O(N)
O(N)，额外空间复杂度
O
(
1
)
O(1)
O(1)
答：
- 引入三个node分别是less，eq，more
- 遍历第一遍，less=第一个<target的节点，eq=第一个=target的节点，more=第一个>target的节点
- 再遍历一遍，小于的再建一个end节点，将小于target的挂在end后面，等于和大于同理
- 将小于区等于区大于区重连
复制含有随机指针节点的链表
方法一：哈希表（字典）
- 节点1复制一个节点1‘(相同val值)放哈希表中去，节点1是key，节点1’是value，同理复制其他的节点
- 节点1的next能找到节点2，random能找到节点3，这个时候通过字典就可以找到节点2‘和节点3’，将节点1‘和这两个节点连接即可
class Solution(object):
def copyRandomList(self, head):
"""
:type head: Node
:rtype: Node
"""
if head==None:
return head
nodemap = dict()
cur = head
while cur!=None:
nodemap[cur] = Node(cur.val)
cur = cur.next
cur = head
while cur!=None:
nodemap[cur].next = nodemap.get(cur.next)
nodemap[cur].random = nodemap.get(cur.random)
cur = cur.next
return nodemap[head]
方法二：
- 构建一个复制节点，连接上1,1’,2,2’,3,3’
- random节点不会相互影响，一次拿出两个节点，1的random是3，3能找到对应的3’，1’的random就可以连到3’上
- 把next分离出来
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
if not head: return
cur = head
# 1. 复制各节点，并构建拼接链表
while cur:
tmp = Node(cur.val)
tmp.next = cur.next
cur.next = tmp
cur = tmp.next
# 2. 构建各新节点的 random 指向
cur = head
while cur:
if cur.random:
cur.next.random = cur.random.next
cur = cur.next.next
# 3. 拆分两链表
cur = res = head.next
pre = head
while cur.next:
pre.next = pre.next.next
cur.next = cur.next.next
pre = pre.next
cur = cur.next
pre.next = None # 单独处理原链表尾节点
return res # 返回新链表头节点
两链表相交
要求时间复杂度 O ( N + M ) O(N+M) O(N+M)，额外空间复杂度 O ( 1 ) O(1) O(1)
判断链表是否有环
要求：返回第一个入环节点
方法一：用hashset，第一个重复的节点就是第一个入环节点
方法二：用一个快指针和一个慢指针，如果快指针指向空，则无环；如果快指针和慢指针相遇了，快指针从头开始变成走1步的，再和慢指针相遇的时候就是第一个入环节点
单链表相交节点
方法一：用hashset，链表1全放进去，查链表2
方法二：先遍历链表1的长度和最后一个节点end1，再遍历链表2的长度和最后一个节点end2，如果end1!=end2，则不可能相交；如果相交的话，找到长度差值len，长的链表先走len步，然后一起走查询相交情况
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
"""
n = 0
tmp_headA = headA
tmp_headB = headB
while tmp_headA!=None:
tmp_headA = tmp_headA.next
n += 1
while tmp_headB!=None:
tmp_headB = tmp_headB.next
n -= 1
if tmp_headA!=tmp_headB:
return
while n>0:
headA = headA.next
n -= 1
while n<0:
headB = headB.next
n += 1
while headA!=None:
if headA == headB:
return headA
headA = headA.next
headB = headB.next
return
方法三：
有环链表相交节点
- 一个链表有环，另外一个链表无环，不可能相交
- 两个链表都有环，已知了loop1和loop2两个入环点：
– A. 各自有环不相交
– B.先相交，再共享一个环（loop1=loop2），可按照无环处理
– C.在环上相交
情况A，loop1一直next没遇到loop2，直到转回loop1
情况C，loop1一直next遇到了loop2，返回loop1或者loop2