题目

Copy List with Random Pointer

思路

O(n),O(n) Map求解

这道题是复制一个链表，特殊的地方是，与一般的链表相比多一个random指针，随机指向链表中的任何一个节点，包括空与自身。那么主要是如何处理这样的一个随机指针。

由于是复制一个链表，因此需要复制每个节点，所以第一次遍历就需要做这个工作。同时引入Map的key-value机制，将原节点的地址与新开辟的对应节点的地址对应起来，这样做的好处就是在下一次遍历时，通过Map就能访问的新开辟节点的链表关系。

题目

Merge K Sorted Lists

思路

除了暴力求解，这道题有两条思路：利用最小堆和分而治之思想。

题目

Swap Nodes in Pairs

思路

链表元素交换，这里的思路遵循了cleancode手册上的思路，为链表增加一个头节点，然后以从头节点开始的三个节点作为一组来进行交换。这里主要考虑的是边界问题。

将新增的头节点作为pre，head作为p，仅当p不为空并且p之后有节点是才进行交换。

下面的交换就是普通的链表next的赋值，但需要重新定位，以便能进行下一次循环。

题目

Merge Two Sorted Lists

思路

主要考虑一些特殊情况，例如有一个链表为空，或者长度不同。这里的方法是创建了一个新的链表头节点，通过遍历原来的两个链表来选择较小的插入到新链表。当一个链表提前结束时，将next指向下一个链表全部插入。最后返回新列表头节点的下一个节点。

最近重拾机器学习，想着学习网上的把Ng课涉及到的几个基础的机器学习算法用python实现以下，第一章的练习就是线性回归的实现。