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

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;
};

//    // 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
}

// This prepends a new value at the beginning of the list
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.
}

// 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(){
int ret = n->data;

delete n;
return ret;
}

// testing
Node* getNode(){
}

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

}
// temporary variances
Node * pre = NULL;
Node * next = NULL;

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

}

}

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

int main(){

//    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)

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

Which means m+k is a multiple of n.