链表作为算法中非常重要的数据结构，在面试中也是非常常用的。

class ListNode:
def __init__(self, x):
self.val = x
self.next = None


## 链表相关面试题

### 如何判断一个链表中存在环？

//
// Created by Bin on 3/28/2017.
//

#include <iostream>
using namespace std;

struct Node{
int data;
Node* next;
};

class LinkedList{
//    // Struct inside the class LinkedList
//    // This is one node which is not needed by the caller. It is just
//    // for internal work.
//    struct Node {
//        int data;
//        Node *next;
//    };

// public member
public:
//constructor
LinkedList(){
head = NULL; // set head to NULL
}

// This prepends a new value at the beginning of the list
void addValue(int val){
Node* n = new Node();   // create new Node
n->data = val;    // set value
n->next = head;     // make the node point to the next node.
// if the list is empty, this is NULL, so the end of the list-->OK
// last but not least, make the head point at the new node.
head = n;
}

// returns the first elements in the list and deletes the Node
// caution, no error-checking here!
// the node in Class doesn't be deleted to free memory?
int popValue(){
Node* n = head;
int ret = n->data;

head = head->next;
delete n;
return ret;
}

// testing
Node* getNode(){
return head;
}

private:
Node* head; // this is the private member variable. It is just a pointer to the first Node
};

// reverse of linked list
Node* reverseByLoop(Node* head){
if(head == NULL || head->next == NULL){
return head;
}
// temporary variances
Node * pre = NULL;
Node * next = NULL;

while(head != NULL){
next = head->next;

head->next = pre;
pre = head;
head = next;
}
return pre;
}
// 第一个条件是判断异常，第二个条件是结束判断
// error detection for the first condition, end decision for the second condition

Node* reverseByRecursion(Node* head){

if(head == NULL || head->next == NULL){
return head;
}

Node* newHead = reverseByRecursion(head->next);

head->next->next = head;
head->next = NULL;

return newHead;
}

void output(Node* head){
if(head == NULL){
cout << "Node is empty!" << endl;
}
Node* next = head;
do{
cout << next->data << endl;
next = next->next;
}
while(next != NULL);
}

int main(){
LinkedList list;

list.addValue(5);
list.addValue(10);
list.addValue(20);

//    output(list.getNode());
//    cout << "After reversing!" << endl;
//    output(reverseByLoop(list.getNode()));
//    output(reverseByRecursion(list.getNode()));

//    cout << list.popValue() << endl;
//    cout << list.popValue() << endl;
//    cout << list.popValue() << endl;

return 0;
}


### 2. 判断有环链表的入口 We can conclude below from above diagram

Distance traveled by fast pointer = 2 * (Distance traveled by slow pointer)

$(m + n*x + k) = 2*(m + n*y + k)$

Note that before meeting the point shown above, fast was moving at twice speed.

x –> Number of complete cyclic rounds made by fast pointer before they meet first time

y –> Number of complete cyclic rounds made by slow pointer before they meet first time

From above equation, we can conclude below

$m + k = (x-2y)*n$

Which means m+k is a multiple of n.