Given a pointer to a node (not the tail node) in a singly linked list. Delete that node from the linked list.

Solution: move the data from the next node into the current node and then deleting the next node. This solution has O(1) runtime.



只给定单链表中某个结点p(非空结点)，在p前面插入一个结点。

办法与前者类似，首先分配一个结点q，将q插入在p后，接下来将p中的数据copy入q中，然后再将要插入的数据记录在p中。

Merging two sorted linked lists

Solution: First of all, compare with each node of two linked list, then insert one by one into a new linked list.

Reverse a Linked-List

Solution: The easiest way is to delete the node one by one, and then create a new linked list to connect the nodes in another direction.

Find kth node of a linked list from end

Solution:
When we travel the linked list, we can keep two pointers. The first pointer moves k steps and the second pointer begins to move. The distance of two pointers are always k-1 steps. When the first pointer arrives at the end of the linked list, the second pointer is pointing the kth node from end.

Time: O(n)



The other similar question:

输入一个单向链表。如果该链表的结点数为奇数，输出中间的结点；如果链表结点数为偶数，输出中间两个结点前面的一个。

Check whether there is the intersection of two linked lists

Given the heads of two linked lists, judge whether there is the intersection of two linked list.

Extend Question:
1. If there is a ring in the linked list, how do you change?
2. Can you find the first intersection node?

Two solutions:
1. We can connect the head of the second linked list to the tail of the first linked list. If there is a ring existing into the new linked list, two linked lists intersects.
Thus, we translated the problem into another problem that checks there is the ring of two linked lists.

2. Firstly, we can travel the first linked list and remember the last node, then travel the next linked list to get the last node. We compare the two last nodes. If they are the same, two linked list intersects.
Time: O(Length(h1)+Length(h2))

After we travels two linked lists, we attain their lengths of two linked lists. The longer one moves (LengthMax - LengthMin), then two linked list move together. If they can find the first same node, it should be the first node they intersects.

Convert a binary search tree into sorted double link list

For example, binary search tree
10
/ \
6 14
/\ /\
4 8 12 16
into double link list:
4=6=8=10=12=14=16

Idea:
The basic idea is that we can get the sorted the elements in the tree by in-order traveling. When we visit one node, we can put this node into the double link list. After traveling the whole tree, we can get a sorted double link list.

The code is as follows:

CASASviz: New Requirements from the Caregivers

At Feb 9th, Heidi, Prafulla and I went to Aging Heath Center at Moscow for inquiring their real needs for our project. These caregivers are very friendly and excited about our project.

The following list is their requirement in need:
1) Anomaly detection: The most worry thing for the caregivers is the safety of the patient in the house. Thus, the safety is the top need for them.
* Leaving home, someone unfamiliar coming home
* Stove and faucet are left open
* Metal in the microwave
* Moving into some dangerous place
* Taking medicine in time

Solution: Based-Rule(Final State Machine) to detect these anomalies. However, we had to make the corresponding rules for them.

2) Monitoring the mobility and Recognizing Activities
* Monitoring the mobility in real time and reviewing history
* Recognize Activities and the Caregivers want to know whether some activities have been finished in right time.

3) Interface
They are very interested into our tool can be implemented on the platform of the smart phones.