本文按照牛客网的顺序，牛客网剑指offer刷题网址：https://www.nowcoder.com/ta/coding-interviews
本篇涉及的题目有：
1、链表中环的入口节点
2、删除链表中的重复结点
3、二叉树的下一个结点
4、对称的二叉树
5、滑动窗口的最大值
1、链表中环的入口节点
问题描述
一个链表中包含环，请找出该链表的环的入口结点。
思路解析
定义两个指针，从头指针开始往后跑。快的指针一次跑两步，慢的指针一次跑一步。如果链表中存在环，且环中假设有n个节点，那么当两个指针相遇时，快的指针刚好比慢的指针多走了环中节点的个数，即n步。从另一个角度想，快的指针比慢的指针多走了慢的指针走过的步数，也是n步。如下图：
上图中，环有5个节点，fast和slow从头节点开始，经过5步相遇。可以看到，如果此时fast指针再从头节点开始走的话，会最终在环的第一个节点和slow指针相遇。大家可以用数学公式证明一下，这里就不做过多的叙述啦。
代码实现
java
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead)
{
if(pHead==null || pHead.next == null || pHead.next.next == null)
return null;
ListNode fast = pHead.next.next;
ListNode slow = pHead.next;
while(fast != slow){
if(fast.next==null || fast.next.next==null)
return null;
fast = fast.next.next;
slow = slow.next;
}
fast = pHead;
while(fast != slow){
fast = fast.next;
slow = slow.next;
}
return fast;
}
}
python
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def EntryNodeOfLoop(self, pHead):
if pHead==None or pHead.next==None or pHead.next.next==None:
return None
low=pHead.next
fast=pHead.next.next
while low!=fast:
if fast.next==None or fast.next.next==None:
return None
low=low.next
fast=fast.next.next
fast=pHead
while low!=fast:
low=low.next
fast=fast.next
return fast
2、删除链表中的重复结点
问题描述
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
思路解析
定义以下几个元素：
p:用于遍历链表；
q：用于记录当前的链表中剩余的元素最后一个；
cur：当前链表节点的值，用于判断时候有重复结点；
flag：记录当前这个值是否有重复结点。
代码实现
java
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ListNode deleteDuplication(ListNode pHead)
{
if(pHead == null)
return null;
ListNode dummy = new ListNode(-1);
dummy.next = pHead;
ListNode q = dummy;
ListNode p = pHead;
int cur = p.val;
boolean flag = true;
while(p!=null){
while(p.next != null && p.next.val == cur){
p = p.next;
flag = false;
}
if(flag){
q.next = p;
q = p;
}
p = p.next;
if(p==null)
break;
cur = p.val;
flag = true;
}
q.next = null;
return dummy.next;
}
}
python
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteDuplication(self, pHead):
# write code here
if not pHead:
return None
dummy = ListNode(-1)
dummy.next = pHead
q = dummy
p = pHead
while p and p.next:
if p.next and p.next.val != p.val:
q.next = p
q = p
p = p.next
elif p.next and p.next.val == p.val:
while p.next and p.next.val==p.val:
p = p.next
p = p.next
q.next = p
return dummy.next
3、二叉树的下一个结点
问题描述
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
思路解析
1、如果这个节点有右子树，那么找到右子树中的最左侧的一个节点并返回
2、如果这个节点没有右子树且是父节点的左子树，直接返回父节点
3、如果这个节点没有右子树且是父节点的右子树，那么我们往上找父节点，找到一个父节点满足： 父节点是父节点的左子树的节点
4、返回None
代码实现
java
/*
public class TreeLinkNode {
int val;
TreeLinkNode left = null;
TreeLinkNode right = null;
TreeLinkNode next = null;
TreeLinkNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public TreeLinkNode GetNext(TreeLinkNode pNode)
{
if(pNode==null)
return null;
if(pNode.right!=null){
TreeLinkNode p = pNode.right;
while(p.left!=null)
p = p.left;
return p;
}
else if(pNode.next!=null){
if(pNode.next.left == pNode)
return pNode.next;
else{
TreeLinkNode p = pNode;
while(p.next!=null){
if(p.next.left == p){
return p.next;
}
p = p.next;
}
return null;
}
}
else
return null;
}
}
python
# -*- coding:utf-8 -*-
# class TreeLinkNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# self.next = None
class Solution:
def GetNext(self, pNode):
# write code here
# 判断是否为空
if not pNode:
return None
if pNode.right:
res = pNode.right
while res.left:
res = res.left
return res
while pNode.next:
tmp = pNode.next
if tmp.left == pNode:
return tmp
pNode = tmp
return None
4、对称的二叉树
问题描述
请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
思路解析
使用递归的思路实现。
代码实现
java
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
boolean isSymmetrical(TreeNode pRoot)
{
return isSymmetricalTree(pRoot,pRoot);
}
private static boolean isSymmetricalTree(TreeNode pRoot,TreeNode qRoot){
if(pRoot==null && qRoot==null)
return true;
else if(pRoot==null || qRoot==null)
return false;
else if(pRoot.val != qRoot.val)
return false;
else
return isSymmetricalTree(pRoot.left,qRoot.right) && isSymmetricalTree(pRoot.right,qRoot.left);
}
}
python
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSymmetrical(self, pRoot):
# write code here
return self.subSymmetrical(pRoot,pRoot)
def subSymmetrical(self,root1,root2):
if not root1 and not root2:
return True
if not root1 or not root2:
return False
if root1.val != root2.val:
return False
return self.subSymmetrical(root1.left,root2.right) and self.subSymmetrical(root1.right,root2.left)
5、滑动窗口的最大值
问题描述
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。
思路解析
我们用双向队列可以在O(N)时间内解决这题。当我们遇到新的数时，将新的数和双向队列的末尾比较，如果末尾比新数小，则把末尾扔掉，
直到该队列的末尾比新数大或者队列为空的时候才住手。这样，我们可以保证队列里的元素是从头到尾降序的，由于队列里只有窗口内的数，
所以他们其实就是窗口内第一大，第二大，第三大...的数。保持队列里只有窗口内数的方法和上个解法一样，也是每来一个新的把窗口最左边的扔掉，
然后把新的加进去。然而由于我们在加新数的时候，已经把很多没用的数给扔了，这样队列头部的数并不一定是窗口最左边的数。这里的技巧是，
我们队列中存的是那个数在原数组中的下标，这样我们既可以直到这个数的值，也可以知道该数是不是窗口最左边的数。这里为什么时间复杂度是O(N)呢？
因为每个数只可能被操作最多两次，一次是加入队列的时候，一次是因为有别的更大数在后面，所以被扔掉，或者因为出了窗口而被扔掉。
因此一个新数进来：
1、判断队列头部的数的下标是否还在窗口中
2、将新数加入到队列中
3、如果index已经达到窗口的大小了，则将队列头部的值加入到返回结果中
代码实现
java
import java.util.*;
public class Solution {
public ArrayList<Integer> maxInWindows(int [] num, int size)
{
ArrayList<Integer> res = new ArrayList<Integer>();
if(size <= 0)
return res;
Deque<Integer> queue = new ArrayDeque<Integer>();
for(int i=0;i<num.length;i++){
if(queue.size()>0 && (i - queue.getFirst()) >= size)
queue.removeFirst();
while(queue.size()>0 && num[i] > num[queue.getLast()])
queue.removeLast();
queue.addLast(i);
if(i+1>=size)
res.add(num[queue.getFirst()]);
}
return res;
}
}
python
# -*- coding:utf-8 -*-
import collections
class Solution:
def maxInWindows(self, num, size):
# write code here
if not num or size<=0:
return []
queue = collections.deque()
res = []
for index,val in enumerate(num):
if len(queue)>0 and (index - queue[0] >= size):
queue.popleft()
while len(queue)>0 and val > num[queue[-1]]:
queue.pop()
queue.append(index)
if index + 1 >= size:
res.append(num[queue[0]])
return res
