1.合并两个有序链表
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例一：
输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4本题主要考察链表的基本操作，代码如下：
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
l = ListNode(None)
head = l
while l1 or l2:
if not l1:
l.next=l2
return head.next
if not l2:
l.next=l1
return head.next
if l1.val<=l2.val:
l.next = l1
l=l.next
l1=l1.next
else:
l.next=l2
l=l.next
l2=l2.next
2.反转链表
反转一个单链表。
示例一：
输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL本题主要考察链表的基本操作，代码如下：
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head:
return None
l = None
p = head
while p:
if p.next==None:
p.next=l
return p
r = p.next
p.next=l
l=p
p=r
3.两数相加
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例一：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807本题我的实现利用了额外的存储空间，从低位到高位依次相加，得到的值除10取商做进位，取余做当前位的结果，代码如下：
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
cin = 0
l3 = ListNode(0)
head = l3
while l1 or l2:
tmp = 0
if l1:
tmp+=l1.val
l1=l1.next
if l2:
tmp+=l2.val
l2=l2.next
tmp+=cin
l3.next=ListNode(tmp%10)
l3= l3.next
cin = tmp/10
if cin>0:
l3.next=ListNode(cin)
return head.next
4.排序链表
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
示例一：
输入: 4->2->1->3 输出: 1->2->3->4
示例二：
输入: -1->5->3->4->0 输出: -1->0->3->4->5本题要求时间复杂度为O(nlogn)，排序算法中快速排序、归并排序和堆排序的时间复杂度为O（nlogn），本文实现了归并排序，代码如下：
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def sortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head==None or head.next==None:
return head
f,s=head,head
while f:
if f.next:
f=f.next
else:
break
if f.next:
f=f.next
s=s.next
else:
break
p=s.next
s.next=None
s=head
p1=self.sortList(s)
p2=self.sortList(p)
return self.merge(p1,p2)
def merge(self,s,p):
if not s:
return p
if not p:
return s
if s.val《p.val:
s.next=self.merge(s.next,p)
return s
else:
p.next=self.merge(s,p.next)
return p
5.环形链表II
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。
示例一：
输入：head = [3,2,0,-4], pos = 1 输出：tail connects to node index 1 解释：链表中有一个环，其尾部连接到第二个节点。
示例二：
输入：head = [1,2], pos = 0 输出：tail connects to node index 0 解释：链表中有一个环，其尾部连接到第一个节点。
示例三：
输入：head = [1], pos = -1 输出：no cycle 解释：链表中没有环。
如上图所示，设置slow指针和fast指针指向head节点，然后指针向前走。fast指针一次移动两步，slow指针一次移动一步。如果链表有环，二者必然会在环中某位置相遇。二者相遇时，slow指针走过的路程为X+Y，fast指针走过的路程为X+Y+Z+Y。而fast指针的速度是slow指针的2倍，因此fast指针走过的路程也就等于2（X+Y）。
此时等式为2（X+Y）=X+2Y+Z，化简可得X=Z。此时，设置指针p指向head，指针q指向当前slow指针位置。然后二者以相同的速度移动，由于X=Z，所以二者必然会在进入循环的位置相遇。此时的指针便指向环形链表的入口。实现代码如下：
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
slow = head
fast = head
while slow:
if fast.next:
fast=fast.next
else:
return None
if fast.next:
fast=fast.next
slow = slow.next
else:
return None
if fast==slow:
p = slow
q = head
while p:
if p==q:
return p
else:
p=p.next
q=q.next
6.相交链表
编写一个程序，找到两个单链表相交的起始节点。
如下面的两个链表：
在节点 c1 开始相交。
示例一：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 输出：Reference of the node with value = 8 输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
示例二：
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 输出：Reference of the node with value = 2 输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例三：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 输出：null 输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。 解释：这两个链表不相交，因此返回 null。
注意：
-
1.如果两个链表没有交点，返回 null.
2.在返回结果后，两个链表仍须保持原有的结构。
3.可假定整个链表结构中没有循环。
4.程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
# 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
"""
p,q=headA,headB
l1,l2=0,0
while p:
l1+=1
p=p.next
while q:
l2+=1
q=q.next
p,q=headA,headB
if l1>=l2:
while l1-l2:
p=p.next
l1-=1
else:
while l2-l1:
q=q.next
l2-=1
while q and p:
if p==q:
return p
else:
q=q.next
p=p.next
return None
7.合并K个排序链表
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例一：
输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3->4->4->5->6本题lists中存储的是链表的头结点，利用一个列表tmp获得当前lists中所有头结点的值，利用min函数找出最小值，获得它在lists中的索引，然后将该节点指针后移，并将该节点插入结果，直至所有列表节点都为空。代码如下：
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
tmp = []
for x in lists:
if x!=None:
tmp.append(x)
lists = tmp
head = ListNode(0)
p = head
while lists:
tmp = [x.val for x in lists]
idx = tmp.index(min(tmp))
n = lists[idx].next
p.next = lists[idx]
p = p.next
p.next = None
if n==None:
lists.pop(idx)
continue
lists[idx] = n
return head.next
8.二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
示例一：
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出: 3 解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例二：
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出: 5 解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。本题利用递归方法，首先是退出递归的条件，当当前节点为None或者等于其中一个要查找的值时，返回当前节点，然后对左子树和右子树进行递归调用。如果两个子树都不为空，则说明查找的两个值在该节点的左子树和右子树上，说明当前节点就是最近公共祖先。如果左子树为空，说明要查找的两个值都在右子树上，因此返回右子树，反之返回左子树。实现代码如下：
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
if root==None or root.val==p.val or root.val==q.val:
return root
l=self.lowestCommonAncestor(root.left,p,q)
r=self.lowestCommonAncestor(root.right,p,q)
if l and r:
return root
elif l:
return l
else:
return r
9.二叉树的锯齿形层次遍历
给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
例如：
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回锯齿形层次遍历如下：
[ [3], [20,9], [15,7] ]本题首先对二叉树进行层次遍历，最后对得到结果，根据层数进行翻转即可。实现代码如下：
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def zigzagLevelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if root==None:
return []
layer = [root]
layer_list = []
while layer:
layer_list.append([x.val for x in layer])
tmp = []
for x in layer:
if x.left:
tmp.append(x.left)
if x.right:
tmp.append(x.right)
layer = tmp
for i in range(len(layer_list)):
if i%2==1:
layer_list[i].reverse()
return layer_list
