链表的题里面，快慢指针、双指针用得很多。
2.1 Write code to remove duplicates from an unsorted linked list.
FOLLOW UP
How would you solve this problem if a temporary buffer is not allowed?
2.2 Implement an algorithm to find the kth to last element of a singly linked list.
2.3 Implement an algorithm to delete a node in the middle of a singly linked list, given only access to that node.
2.4 Write code to partition a linked list around a value x, such that all nodes less than x come before alt nodes greater than or equal to x.
Leetcode上有，点此。
2.5 You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1 's digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.
Leetcode上有，点此。
FOLLOW UP
Suppose the digits are stored in forward order. Repeat the above problem.
reverse之后求后然后再reverse结果，careercup上的做法更inefficient。
2.6 Given a circular linked list, implement an algorithm which returns the node at the beginning of the loop.
Leetcode上有，点此。
2.7 Implement a function to check if a linked list is a palindrome,
naive的方法就是把list reverse一下，然后和原串比较。
更好的方法是用stack，比较前半部分还是很巧妙的。stack用来reverse也是比较直观的。注意奇偶长度的list。
递归的方法理解起来更难些。传递指针的指针，使得递归调用后，指针move到对应的镜像位置上了。这一点和Leetcode上Convert Sorted List to Binary Search Tree类似。
struct ListNode {
int val;
ListNode* next;
ListNode(int v) : val(v), next(NULL) {}
};
class XList {
public:
XList(int n) {
srand(time(NULL));
head = NULL;
for (int i = ; i < n; ++i) {
ListNode* next = new ListNode(rand() % );
next->next = head;
head = next;
}
len = n;
}
XList(XList ©) {
//cout << "copy construct" << endl;
len = copy.size();
if (len == ) return;
head = new ListNode(copy.head->val);
ListNode *p = copy.head->next, * tail = head;
while (p != NULL) {
tail->next = new ListNode(p->val);
tail = tail->next;
p = p->next;
}
}
~XList() {
ListNode *tmp = NULL;
while (head != NULL) {
tmp = head->next;
delete head;
head = tmp;
}
}
// 2.1(1)
void removeDups() {
if (head == NULL) return;
map<int, bool> existed;
ListNode* p = head, *pre = NULL;
while (p != NULL) {
if (existed[p->val]) {
pre->next = p->next;
len--;
delete p;
p = pre->next;
} else {
pre = p;
existed[p->val] = true;
p = p->next;
}
}
}
//2.1(2)
void removeDups2() {
ListNode *p = head;
while (p != NULL) {
ListNode *next = p;
while (next->next) {
if (next->next->val == p->val) {
ListNode *tmp = next->next;
len--;
delete next->next;
next->next = tmp->next;
} else {
next = next->next; // only move to next in the 'else' block
}
}
p = p->next;
}
}
// 2.2(1)
ListNode* findKthToLast(int k) {
if (head == NULL) return NULL;
if (k <= ) return NULL; // more efficient
ListNode *fast = head, *slow = head;
int i = ;
for (; i < k && fast; ++i) {
fast = fast->next;
}
if (i < k) return NULL;
while (fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
//2.2(2)
ListNode* findKthToLast2(int k) {
return recursiveFindKthToLast(head, k);
}
//2.2(2)
ListNode* recursiveFindKthToLast(ListNode *h, int &k) {
if (h == NULL) {
return NULL;
}
// should go to the end
ListNode *ret = recursiveFindKthToLast(h->next, k);
k--;
if (k == ) return h;
return ret;
}
// 2.3
bool deleteNode(ListNode* node) {
if (node == NULL || node->next == NULL) return false; // in the middle, head is also ok, because we don't delete node itself
ListNode *next = node->next;
node->val = next->val;
node->next = next->next;
len--;
delete next;
return true;
}
// 2.4
void partition(int x) {
if (head == NULL) return;
ListNode less(), greater();
ListNode* p = head, *p1 = &less, *p2 = &greater;
while (p) {
if (p->val < x) {
p1->next = p;
p1 = p1->next;
} else {
p2->next = p;
p2 = p2->next;
}
p = p->next;
}
p1->next = greater.next;
head = less.next;
}
// 2.7(1)
bool isPalindrome() {
if (head == NULL) return true;
stack<ListNode*> st;
ListNode *fast = head, *slow = head;
while (fast && fast->next) {
st.push(slow);
slow = slow->next;
fast = fast->next->next;
}
if (fast) slow = slow->next; // fast->next = null, odd number, skip the middle one
while (slow) {
if (slow->val != st.top()->val) return false;
slow = slow->next;
st.pop();
}
return true;
}
// 2.7(2)
bool isPalindrome2() {
ListNode* h = head;
return recursiveIsPalindrome(h, len);
}
bool recursiveIsPalindrome(ListNode* &h, int l) { // note that h is passed by reference
if (l <= ) return true;
if (l == ) {
h = h->next; // move, when odd
return true;
}
if (h == NULL) return true;
int v1 = h->val;
h = h->next;
if (!recursiveIsPalindrome(h, l - )) return false;
int v2 = h->val;
h = h->next;
cout << v1 << " vs. " << v2 << endl;
return v1 == v2;
}
void print() const {
ListNode *p = head;
while (p != NULL) {
cout << p->val << "->";
p = p->next;
}
cout << "NULL(len: " << len << ")" << endl;
}
int size() const {
return len;
}
void insert(int v) {
len++;
ListNode *node = new ListNode(v);
node->next = head;
head = node;
}
private:
ListNode *head;
int len;
};