382. Linked List Random Node

In first place, I don't have any clue. Then I followed the top rated solution which uses "reservoir sampling". Here is the wiki page for this algorithm: https://en.wikipedia.org/wiki/Reservoir_sampling.

For example, the list is 1->2->3.
1. First of all , we keep 1st node. in the list. The probability is 1.

2. We reach the 2nd node. We have two choices:
(1). keep the current node. Then the probability is 1/2
(2). discard the current node, keep the 2nd node. Then the probability is 1/2.

3. We reach the 3rd node. We have two choices:
(1). keep the current node. So the probability for discarding the 3rd node is 2/3. Since the current node could be 1st node or 2nd node, the probability for keeping the current node is 1/2*2/3 = 1/3.
(2). keep the 3rd node. So the probability is simply 1/3.

By introduction, it is easy to prove that when there is n nodes, each node is kept for probability 1/n. With this in mind, here is the solution:

1:  /**  
2:   * Definition for singly-linked list.  
3:   * struct ListNode {  
4:   *   int val;  
5:   *   ListNode *next;  
6:   *   ListNode(int x) : val(x), next(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  private:  
11:    ListNode *head = NULL;  
12:  public:  
13:    /** @param head The linked list's head.  
14:      Note that the head is guaranteed to be not null, so it contains at least one node. */  
15:    Solution(ListNode* head) {  
16:      this->head = head;  
17:    }  
18:    /** Returns a random node's value. */  
19:    int getRandom() {  
20:      ListNode *cur = head->next;  
21:      ListNode *res = head;  
22:      for (int n = 2; cur != NULL; n++) {  
23:        if (rand() % n == 0) res = cur;  
24:        cur = cur->next;  
25:      }  
26:      return res->val;;  
27:    }  
28:  };  
29:  /**  
30:   * Your Solution object will be instantiated and called as such:  
31:   * Solution obj = new Solution(head);  
32:   * int param_1 = obj.getRandom();  
33:   */  

Memory Allocator

This question is asked in one of my phone interview. The question is "To  implement a memory allocator that allows multiple clients to allocate and free memory from a buffer". My initial thought is the maintain a front and rear pointer and make the buffer as a ring. However, such design doesn't satisfy the requirement because there are multiple users for example, user1 has requested buffer[0-3], user2 has requested buffer[4-6] and user3 has requested buffer[7]. When user2 releases his buffer before user3, you'll get a problem because of memory fragmentation. You can't simply move the front pointer back to 4 because it'll release user3's buffer which is being used currently. So I thought of the way how Linux kernel maintains the memory.  I'll need a pointer that maintains a list of free memory chunk. Yes, it is a linked list because of the memory fragmentation. When you request a piece of memory, you'll check the list to see if there is any memory fragment that has enough space for the request. If so, update the offset pointer for that node. Otherwise, return NULL pointer.

 #include <stdio.h>  
 #include <stdlib.h>  
 // To execute C, please define "int main()"  
 static char buffer[256];  
 struct LinkNode {  
  int start;  
  int end;  
  struct LinkNode *next;  
 };  
 static struct LinkNode *free_header = NULL;  
 void initFreeMemory();  
 void *allocate(int size);  
 int main() {  
  initFreeMemory();  
  printf("%p\n", buffer);  
  void *addr1 = allocate(3);  
  printf("%p\n", addr1);  
  void *addr2 = allocate(128);  
  printf("%p\n", addr2);  
  printf("%p\n", buffer+free_header->start);  
  return 0;  
 }  
 void initFreeMemory() {  
  free_header = (struct LinkNode *)malloc(sizeof(struct LinkNode));  
  free_header->start = 0;  
  free_header->end = 256;  
  free_header->next = NULL;  
 }  
 void *allocate(int size) {  
  struct LinkNode *p = free_header;  
  while (p) {  
   if (p->end - p->start >= size) break;  
   p = p->next;  
  }  
  if (p == NULL) return NULL;  
  void *ret = buffer+p->start;  
  p->start += size;  
  return ret;  
 }  
 /*void free(void *object) {  
  int size = sizeof(object);  
  struct LinkNode *node = malloc(sizeof(struct LinkNode));  
  node->start = object;  
  node->end = node->start + size;  
  free_header->next = node;  
 }*/  

160. Intersection of Two Linked Lists

I count the number of the two lists first. And then I compute the offset and move the head pointer of the longer list to the offset. And from there compare the two lists and check the intersection.

1:  /**  
2:   * Definition for singly-linked list.  
3:   * struct ListNode {  
4:   *   int val;  
5:   *   ListNode *next;  
6:   *   ListNode(int x) : val(x), next(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {  
12:      int a = countList(headA);  
13:      int b = countList(headB);  
14:      int diff = 0;  
15:      if (a > b) {  
16:        diff = a - b;  
17:        while (diff) { headA = headA->next; diff--; }  
18:      } else {  
19:        diff = b - a;  
20:        while (diff) { headB = headB->next; diff--; }  
21:      }  
22:      while (headA != headB) {  
23:        headA = headA->next;  
24:        headB = headB->next;  
25:      }  
26:      return headA;  
27:    }  
28:    int countList(ListNode *head) {  
29:      int count = 0;  
30:      while (head) {  
31:        head = head->next;  
32:        count++;  
33:      }  
34:      return count;  
35:    }  
36:  };  

234. Palindrome Linked List

I count the total nodes first and then find the middle node. To cover both cases of odd/even number, the middle node should be the ceiling of n / 2. And then reverse the sublist starting from the middle node. After that, compare the first half list with the reversed second half list to see if any discrepancy.

1:  /**  
2:   * Definition for singly-linked list.  
3:   * struct ListNode {  
4:   *   int val;  
5:   *   ListNode *next;  
6:   *   ListNode(int x) : val(x), next(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    bool isPalindrome(ListNode* head) {  
12:      int count = countList(head);  
13:      if (count < 2) return true;  
14:      int mid = (count+1)/2;  
15:      ListNode *l2 = head;  
16:      while (mid) {  
17:        l2 = l2->next;  
18:        mid--;  
19:      }  
20:      l2 = reverseList(l2);  
21:      while (l2) {  
22:        if (head->val != l2->val) return false;  
23:        head = head->next;  
24:        l2 = l2->next;  
25:      }  
26:      return true;  
27:    }  
28:    int countList(ListNode *head) {  
29:      int count = 0;  
30:      while(head) {  
31:        count++;  
32:        head = head->next;  
33:      }  
34:      return count;  
35:    }  
36:    ListNode *reverseList(ListNode *head) {  
37:      ListNode *pre = NULL;  
38:      while (head) {  
39:        ListNode *next = head->next;  
40:        head->next = pre;  
41:        pre = head;  
42:        head = next;  
43:      }  
44:      return pre;  
45:    }  
46:  };  

21. Merge Two Sorted Lists

Well, this is a real easy one.

1:  /**  
2:   * Definition for singly-linked list.  
3:   * struct ListNode {  
4:   *   int val;  
5:   *   ListNode *next;  
6:   *   ListNode(int x) : val(x), next(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {  
12:      ListNode *dummy = new ListNode(-1);  
13:      ListNode *cur = dummy;  
14:      while (l1 && l2) {  
15:        if (l1->val < l2->val) { cur->next = l1; l1 = l1->next; }  
16:        else { cur->next = l2; l2 = l2->next; }  
17:        cur = cur->next;  
18:      }  
19:      if (l1) cur->next = l1;  
20:      if (l2) cur->next = l2;  
21:      cur = dummy->next;  
22:      delete dummy;  
23:      return cur;  
24:    }  
25:  };  

141. Linked List Cycle

To find a cycle in the linked list, we can have two pointers, one of which moves one steps once and the other moves two steps once. If the fast pointer reaches NULL, it means there is no cycle, otherwise, the fast pointer will capture the slow pointer again.

1:  /**  
2:   * Definition for singly-linked list.  
3:   * struct ListNode {  
4:   *   int val;  
5:   *   ListNode *next;  
6:   *   ListNode(int x) : val(x), next(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    bool hasCycle(ListNode *head) {  
12:      if (head == NULL || head->next == NULL) return false;  
13:      ListNode *slow = head;  
14:      ListNode *fast = head->next;  
15:      while (fast && fast->next) {  
16:        slow = slow->next;  
17:        fast = fast->next->next;  
18:        if (slow == fast) return true;  
19:      }  
20:      return false;  
21:    }  
22:  };  

138. Copy List with Random Pointer

I used hash map to solve the problem with two rounds.
In first round, copy the list without regard with random pointer but make a map between the old node and new node.
In the second round, fix the random pointer by the hash mapping.

1:  /**  
2:   * Definition for singly-linked list with a random pointer.  
3:   * struct RandomListNode {  
4:   *   int label;  
5:   *   RandomListNode *next, *random;  
6:   *   RandomListNode(int x) : label(x), next(NULL), random(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    RandomListNode *copyRandomList(RandomListNode *head) {  
12:      unordered_map<RandomListNode*, RandomListNode*> mp;  
13:      RandomListNode *dummy = new RandomListNode(-1);  
14:      RandomListNode *cur = head, *res = dummy;  
15:      while (cur) {  
16:        RandomListNode *node = new RandomListNode(cur->label);  
17:        mp[cur] = node;  
18:        res->next = node;  
19:        res = res->next;  
20:        cur = cur->next;  
21:      }  
22:      cur = head;  
23:      res = dummy->next;  
24:      while (cur) {  
25:        if (cur->random != NULL) {  
26:          res->random = mp[cur->random];  
27:        }  
28:        res = res->next;  
29:        cur = cur->next;  
30:      }  
31:      res = dummy->next;  
32:      delete dummy;  
33:      return res;  
34:    }  
35:  };  

206. Reverse Linked List

I had following code in first place.

1:  /**  
2:   * Definition for singly-linked list.  
3:   * struct ListNode {  
4:   *   int val;  
5:   *   ListNode *next;  
6:   *   ListNode(int x) : val(x), next(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    ListNode* reverseList(ListNode* head) {  
12:      if (head == NULL || head->next == NULL) return head;  
13:      ListNode *prev = head, *cur = head->next;  
14:      prev->next = NULL;  
15:      while (cur) {  
16:        ListNode *tmp = cur->next;  
17:        cur->next = prev;  
18:        prev = cur;  
19:        cur = tmp;  
20:      }  
21:      return prev;  
22:    }  
23:  };  

And here is the more concise one from top rated solution.

1:  /**  
2:   * Definition for singly-linked list.  
3:   * struct ListNode {  
4:   *   int val;  
5:   *   ListNode *next;  
6:   *   ListNode(int x) : val(x), next(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    ListNode* reverseList(ListNode* head) {  
12:      ListNode *prev = NULL;  
13:      while (head) {  
14:        ListNode *tmp = head->next;  
15:        head->next = prev;  
16:        prev = head;  
17:        head = tmp;  
18:      }  
19:      return prev;  
20:    }  
21:  };  

369. Plus One Linked List

Well, I was thinking reverse the list, do increase and reverse the list again in first place. However, I don't think it is expected in the interview because this is so naive. And particularly, if we are not allowed to change the list order then this solution is out. Actually, we can do recursive way because recursion helps us "reverse" the list.

1:  /**  
2:   * Definition for singly-linked list.  
3:   * struct ListNode {  
4:   *   int val;  
5:   *   ListNode *next;  
6:   *   ListNode(int x) : val(x), next(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    ListNode* plusOne(ListNode* head) {  
12:      if (dfs(head) == 0) return head;  
13:      else {  
14:        ListNode *node = new ListNode(1);  
15:        node->next = head;  
16:        return node;  
17:      }  
18:    }  
19:    int dfs(ListNode *head) {  
20:      if (head == NULL) return 1;  
21:      int carry = dfs(head->next);  
22:      if (carry == 0) return 0;  
23:      int val = head->val + 1;  
24:      head->val = val % 10;  
25:      return val / 10;  
26:    }  
27:  };  

25. Reverse Nodes in k-Group

The trick I noticed here is the first node of sublist will be the end of the new list and will be the new "dummy" node for the next new list. And we mustn't forget the end node's next should be updated every time we reverse the sublist.

1:  /**  
2:   * Definition for singly-linked list.  
3:   * struct ListNode {  
4:   *   int val;  
5:   *   ListNode *next;  
6:   *   ListNode(int x) : val(x), next(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    ListNode* reverseKGroup(ListNode* head, int k) {  
12:      if (k <= 1) return head;  
13:      ListNode *dummy = new ListNode(0);  
14:      dummy->next = head;  
15:      ListNode *prev = dummy, *cur = prev->next;  
16:      while (cur) {  
17:        int count = k;  
18:        while (cur && count) {  
19:          cur = cur->next;  
20:          count--;  
21:        }  
22:        if (count) break;  
23:        ListNode *end = prev->next;  
24:        ListNode *p = end->next;  
25:        while (p != cur) {  
26:          end->next = p->next;  
27:          p->next = prev->next;  
28:          prev->next = p;  
29:          p = end->next;  
30:        }  
31:        prev = end;  
32:      }  
33:      head = dummy->next;  
34:      delete dummy;  
35:      return head;  
36:    }  
37:  };  

23. Merge k Sorted Lists

A typical divide and conquer solution. We need to find the correct termination condition. I use "if (lo > hi) return NULL" as termination condition but got run time error. We should terminate at two conditions:
1. lo == hi, return lists[lo]
2. lo+1 == hi, merge lists[lo] and lists[hi] and return.

1:  /**  
2:   * Definition for singly-linked list.  
3:   * struct ListNode {  
4:   *   int val;  
5:   *   ListNode *next;  
6:   *   ListNode(int x) : val(x), next(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    ListNode* mergeKLists(vector<ListNode*>& lists) {  
12:      if (lists.size() == 0) return NULL;  
13:      if (lists.size() == 1) return lists[0];  
14:      return sortLists(lists, 0, (int)lists.size()-1);  
15:    }  
16:    ListNode *sortLists(vector<ListNode*> &lists, int lo, int hi) {  
17:      if (lo == hi) return lists[lo];  
18:      if (lo+1 == hi) return merge(lists[lo], lists[hi]);  
19:      int mid = lo + (hi - lo) / 2;  
20:      ListNode *l1 = sortLists(lists, lo, mid-1);  
21:      ListNode *l2 = sortLists(lists, mid, hi);  
22:      return merge(l1, l2);  
23:    }  
24:    ListNode *merge(ListNode *l1, ListNode *l2) {  
25:      ListNode *dummy = new ListNode(-1);  
26:      ListNode *cur = dummy;  
27:      while (l1 && l2) {  
28:        if (l1->val < l2->val) {  
29:          cur->next = l1;  
30:          l1 = l1->next;  
31:        } else {  
32:          cur->next = l2;  
33:          l2 = l2->next;  
34:        }  
35:        cur = cur->next;  
36:      }  
37:      if (l1) cur->next = l1;  
38:      if (l2) cur->next = l2;  
39:      cur = dummy->next;  
40:      delete dummy;  
41:      return cur;  
42:    }  
43:  };  

When I revisited this problem, the terminal condition can be simplified to:
1. s == e, return lists[s]; 2. s > e, return NULL.

1:  /**  
2:   * Definition for singly-linked list.  
3:   * struct ListNode {  
4:   *   int val;  
5:   *   ListNode *next;  
6:   *   ListNode(int x) : val(x), next(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    ListNode* mergeKLists(vector<ListNode*>& lists) {  
12:      return helper(lists, 0, lists.size()-1);  
13:    }  
14:    ListNode *helper(vector<ListNode*> &lists, int s, int e) {  
15:      if (s == e) return lists[s];  
16:      if (s > e) return NULL;  
17:      int mid = s + (e - s) / 2;  
18:      ListNode *l1 = helper(lists, s, mid);  
19:      ListNode *l2 = helper(lists, mid+1, e);  
20:      ListNode *dummy = new ListNode(-1);  
21:      ListNode *cur = dummy;  
22:      while (l1 && l2) {  
23:         if (l1->val < l2->val) {  
24:           cur->next = l1;  
25:           l1 = l1->next;  
26:         } else {  
27:           cur->next = l2;  
28:           l2 = l2->next;  
29:         }  
30:         cur = cur->next;  
31:      }  
32:      if (l1) cur->next = l1;  
33:      if (l2) cur->next = l2;  
34:      cur = dummy->next;  
35:      delete dummy;  
36:      return cur;  
37:    }  
38:  };  

61. Rotate List

This can be solved in O(n) running time. The idea is straightforward, i.e. move to the starting point where the list rotates, connect the end to the head and return the starting point.

1:  /**  
2:   * Definition for singly-linked list.  
3:   * struct ListNode {  
4:   *   int val;  
5:   *   ListNode *next;  
6:   *   ListNode(int x) : val(x), next(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    ListNode* rotateRight(ListNode* head, int k) {  
12:      if (head == NULL || head->next == NULL) return head;  
13:      int n = countList(head);  
14:      int r = k % n;  
15:      if (r == 0) return head;  
16:      int m = n - r;  
17:      ListNode *cur = head, *start = NULL, *end = NULL;  
18:      while (--m) {  
19:        cur = cur->next;  
20:      }  
21:      end = cur;  
22:      start = cur->next;  
23:      while (cur->next) {  
24:        cur = cur->next;  
25:      }  
26:      cur->next = head;  
27:      end->next = NULL;  
28:      return start;  
29:    }  
30:    int countList(ListNode *head) {  
31:      int count = 0;  
32:      while (head) {  
33:        count++;  
34:        head = head->next;  
35:      }  
36:      return count;  
37:    }  
38:  };  

143. Reorder List

Three steps:
(1) cut into two lists (note the first list must be longer or equal to the second list).
(2) reverse the second list.
(3) merge the two lists.

1:  /**  
2:   * Definition for singly-linked list.  
3:   * struct ListNode {  
4:   *   int val;  
5:   *   ListNode *next;  
6:   *   ListNode(int x) : val(x), next(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    void reorderList(ListNode* head) {  
12:      if (head == NULL || head->next == NULL) return;  
13:      int count = countList(head);  
14:      count = (count + 1) / 2;  
15:      ListNode *prev = NULL, *cur = head;  
16:      while (count) {  
17:        count--;  
18:        prev = cur;  
19:        cur = cur->next;  
20:      }  
21:      prev->next = NULL;  
22:      ListNode *l1 = head;  
23:      ListNode *l2 = reverseList(cur);  
24:      while (l2) {  
25:        ListNode *tmp = l2->next;  
26:        l2->next = l1->next;  
27:        l1->next = l2;  
28:        l1 = l2->next;  
29:        l2 = tmp;  
30:      }  
31:      return;  
32:    }  
33:    int countList(ListNode* head) {  
34:      int count = 0;  
35:      while (head) {  
36:        count++;  
37:        head = head->next;  
38:      }  
39:      return count;  
40:    }  
41:    ListNode *reverseList(ListNode *head) {  
42:      ListNode *dummy = new ListNode(-1);  
43:      ListNode *cur = head;  
44:      while (cur) {  
45:        ListNode *tmp = cur;  
46:        cur = cur->next;  
47:        tmp->next = dummy->next;  
48:        dummy->next = tmp;  
49:      }  
50:      head = dummy->next;  
51:      delete dummy;  
52:      return head;  
53:    }  
54:  };  

2. Add Two Numbers

Well, the code I wrote is long and tedious. It can be optimized for sure but it’s good enough for the interview because optimizing code is very volatile to errors. When I revisit this problem, I made mistake in line 40 - 43.

1:  /**  
2:   * Definition for singly-linked list.  
3:   * struct ListNode {  
4:   *   int val;  
5:   *   ListNode *next;  
6:   *   ListNode(int x) : val(x), next(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {  
12:      ListNode *dummy = new ListNode(-1);  
13:      ListNode *cur = dummy;  
14:      int carry = 0;  
15:      while (l1 && l2) {  
16:        int sum = l1->val + l2->val + carry;  
17:        carry = sum/10;  
18:        ListNode *node = new ListNode(sum%10);  
19:        cur->next = node;  
20:        cur = cur->next;  
21:        l1 = l1->next;  
22:        l2 = l2->next;  
23:      }  
24:      while (l1) {  
25:        int sum = l1->val + carry;  
26:        carry = sum/10;  
27:        ListNode *node = new ListNode(sum%10);  
28:        cur->next = node;  
29:        cur = cur->next;  
30:        l1 = l1->next;  
31:      }  
32:      while (l2) {  
33:        int sum = l2->val + carry;  
34:        carry = sum/10;  
35:        ListNode *node = new ListNode(sum%10);  
36:        cur->next = node;  
37:        cur = cur->next;  
38:        l2 = l2->next;  
39:      }  
40:      if (carry) {  
41:        ListNode *node = new ListNode(1);  
42:        cur->next = node;  
43:      }  
44:      cur = dummy->next;  
45:      delete dummy;  
46:      return cur;  
47:    }  
48:  };  

148. Sort List

A typical divide and conquer solution.

1:  /**  
2:   * Definition for singly-linked list.  
3:   * struct ListNode {  
4:   *   int val;  
5:   *   ListNode *next;  
6:   *   ListNode(int x) : val(x), next(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    ListNode* sortList(ListNode* head) {  
12:      if (head == NULL || head->next == NULL) return head;  
13:      ListNode *slow = head, *fast = head, *prev = NULL;  
14:      while (fast && fast->next) {  
15:        prev = slow;  
16:        slow = slow->next;  
17:        fast = fast->next->next;  
18:      }  
19:      prev->next = NULL;  
20:      ListNode *l1 = sortList(head);  
21:      ListNode *l2 = sortList(slow);  
22:      ListNode *dummy = new ListNode(-1);  
23:      ListNode *cur = dummy;  
24:      while (l1 && l2) {  
25:        if (l1->val < l2->val) {  
26:          cur->next = l1;  
27:          l1 = l1->next;  
28:        } else {  
29:          cur->next = l2;  
30:          l2 = l2->next;  
31:        }  
32:        cur = cur->next;  
33:      }  
34:      if (l1) cur->next = l1;  
35:      if (l2) cur->next = l2;  
36:      cur = dummy->next;  
37:      delete dummy;  
38:      return cur;  
39:    }  
40:  };  

92. Reverse Linked List II

This problem can be done in two parts.
(1) move pointer to position m.
(2) reverse sublist from m to n. Note, the first node in the sublist will be the tail in the reversed list so we just need to move the node behind it to the head of the sublist by insertion. Also note prev->next will always be the head of the sublist no matter it is done with the reverse.

I made several mistakes here.
(1) In line 23, I was trying to link p->next to cur. This is true for the first round but it is wrong since then because cur is moved forward by inserting a tail node before it. Instead, we are inserting tail node before head which is actually prev->next.
(2) I was trying to move prev to next. Note, prev is always fixed here as in the sublist, we try to insert tail node before head which is right after prev.
(3) I was trying to compute n after line 17. Note after line 17, m has become 0.

1:  /**  
2:   * Definition for singly-linked list.  
3:   * struct ListNode {  
4:   *   int val;  
5:   *   ListNode *next;  
6:   *   ListNode(int x) : val(x), next(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    ListNode* reverseBetween(ListNode* head, int m, int n) {  
12:      if (m == n) return head;  
13:      n -= m;  
14:      ListNode *dummy = new ListNode(-1);  
15:      dummy->next = head;  
16:      ListNode *prev = dummy;  
17:      while (--m) prev = prev->next;  
18:      ListNode *cur = prev->next;  
19:      // we don't need to move prev.  
20:      while (n--) {  
21:        ListNode *p = cur->next;  
22:        cur->next = p->next;  
23:        p->next = prev->next;  
24:        prev->next = p;  
25:      }  
26:      return dummy->next;  
27:    }  
28:  };  

147. Insertion Sort List

Similar to "86. Partition List", don't forget to process a special case where no insertion is needed.

1:  /**  
2:   * Definition for singly-linked list.  
3:   * struct ListNode {  
4:   *   int val;  
5:   *   ListNode *next;  
6:   *   ListNode(int x) : val(x), next(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    ListNode* insertionSortList(ListNode* head) {  
12:      ListNode *dummy = new ListNode(-1);  
13:      dummy->next = head;  
14:      ListNode *head_prev = dummy;  
15:      while (head) {  
16:        ListNode *prev = dummy, *cur = dummy->next;  
17:        while (cur->val < head->val) {  
18:          prev = cur;  
19:          cur = cur->next;  
20:        }  
21:        if (cur == head) {
22:          head_prev = head;  
23:          head = head->next;  
24:        } else {  
25:          head_prev->next = head->next;  
26:          head->next = cur;  
27:          prev->next = head;  
28:          head = head_prev->next;  
29:        }  
30:      }  
31:      return dummy->next;  
32:    }  
33:  };  

Then code above only beats 24%, so it can be improved to beat 80%

1:  /**  
2:   * Definition for singly-linked list.  
3:   * struct ListNode {  
4:   *   int val;  
5:   *   ListNode *next;  
6:   *   ListNode(int x) : val(x), next(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    ListNode* insertionSortList(ListNode* head) {  
12:      ListNode *dummy = new ListNode(-1);  
13:      dummy->next = head;  
14:      ListNode *prev = dummy, *cur = head;  
15:      while (cur) {  
16:        if (cur->next && cur->next->val < cur->val) {  
17:          while (prev->next && prev->next->val < cur->next->val) {  
18:            prev = prev->next;  
19:          }  
20:          ListNode *tmp = cur->next->next;  
21:          cur->next->next = prev->next;  
22:          prev->next = cur->next;  
23:          cur->next = tmp;  
24:          prev = dummy;  
25:        } else {  
26:          cur = cur->next;  
27:        }  
28:      }  
29:      return dummy->next;  
30:    }  
31:  };  

When I revisited this problem, I had a more concise solution.

1:  /**  
2:   * Definition for singly-linked list.  
3:   * struct ListNode {  
4:   *   int val;  
5:   *   ListNode *next;  
6:   *   ListNode(int x) : val(x), next(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    ListNode* insertionSortList(ListNode* head) {  
12:      if (head == NULL) return NULL;  
13:      ListNode *dummy = new ListNode(-1);  
14:      ListNode *cur = head->next;  
15:      dummy->next = head, head->next = NULL;  
16:      while (cur) {  
17:        ListNode *p = dummy, *q = dummy->next;  
18:        while (q && q->val < cur->val) { p = q; q = q->next; }  
19:        p->next = cur;  
20:        cur = cur->next;  
21:        p->next->next = q;  
22:      }  
23:      head = dummy->next;  
24:      delete dummy;  
25:      return head;  
26:    }  
27:  };  

86. Partition List

My solution is to keep one pointer as the tail of list that is less than x. It also can be interpreted as the position to insert for next element less than x. I forget to deal with a special case where the first element is less than x and got LTE.

1:  /**  
2:   * Definition for singly-linked list.  
3:   * struct ListNode {  
4:   *   int val;  
5:   *   ListNode *next;  
6:   *   ListNode(int x) : val(x), next(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    ListNode* partition(ListNode* head, int x) {  
12:      ListNode *dummy = new ListNode(-1);  
13:      ListNode *prev = dummy, *cur = head, *par = dummy;  
14:      dummy->next = head;  
15:      while (cur) {  
16:        if (cur->val < x) {  
17:          if (prev == par) {  
18:            cur = cur->next;  
19:            prev = prev->next;  
20:            par = par->next;  
21:          } else {  
22:            prev->next = cur->next;  
23:            cur->next = par->next;  
24:            par->next = cur;  
25:            cur = prev->next;  
26:            par = par->next;  
27:          }  
28:        } else {  
29:          prev = cur;  
30:          cur = cur->next;  
31:        }  
32:      }  
33:      return dummy->next;  
34:    }  
35:  };  

Another solution will be separate the list into two lists and combine them in the end.

When I revisited this problem, I had a bit more concise solution.

1:  /**  
2:   * Definition for singly-linked list.  
3:   * struct ListNode {  
4:   *   int val;  
5:   *   ListNode *next;  
6:   *   ListNode(int x) : val(x), next(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    ListNode* partition(ListNode* head, int x) {  
12:      ListNode *dummy = new ListNode(-1);  
13:      ListNode *small = dummy;  
14:      ListNode *large = head, *large_head = NULL, *large_prev = NULL;  
15:      while (large) {  
16:        if (large->val < x) {  
17:          small->next = large;  
18:          large = large->next;  
19:          if (large_prev) large_prev->next = large;  
20:          small = small->next;  
21:          small->next = NULL;  
22:        } else {  
23:          if (large_head == NULL) large_head = large;  
24:          large_prev = large;  
25:          large = large->next;  
26:        }  
27:      }  
28:      small->next = large_head;  
29:      head = dummy->next;  
30:      delete dummy;  
31:      return head;  
32:    }  
33:  };  

109. Convert Sorted List to Binary Search Tree

The intuitive idea is to recursively construct binary search tree. There are two ways. First solution is using a counter.

1:  class Solution {  
2:  public:  
3:    TreeNode* sortedListToBST(ListNode* head) {  
4:      int len = 0;  
5:      ListNode *cur = head;  
6:      while (cur) {  
7:        len++;  
8:        cur = cur->next;  
9:      }  
10:      return helper(head, len);  
11:    }  
12:    TreeNode *helper(ListNode* head, int len) {  
13:      if (len == 0) return NULL;  
14:      int half = len / 2;  
15:      ListNode *cur = head;  
16:      for (int i = 0; i < half; i++) {  
17:        cur = cur->next;  
18:      }  
19:      TreeNode *node = new TreeNode(cur->val);  
20:      TreeNode *left = helper(head, half);  
21:      TreeNode *right = helper(cur->next, len-half-1);  
22:      node->left = left;  
23:      node->right = right;  
24:      return node;  
25:    }  
26:  };  

The second solution uses slow and fast pointer to find the middle node. This is a little bit faster than the first one because it saves one entire list scan.

1:  class Solution {  
2:  public:  
3:    TreeNode* sortedListToBST(ListNode* head) {  
4:      if (head == NULL) return NULL;  
5:      ListNode *slow = head, *fast = head, *prev = NULL;  
6:      while (fast && fast->next) {  
7:        prev = slow;  
8:        slow = slow->next;  
9:        fast = fast->next->next;  
10:      }  
11:      if (prev == NULL) head = NULL;  
12:      else prev->next = NULL;  
13:      TreeNode *node = new TreeNode(slow->val);  
14:      node->left = sortedListToBST(head);  
15:      node->right = sortedListToBST(slow->next);  
16:      return node;  
17:    }  
18:  };  

142. Linked List Cycle II

I'm inspired by this blog which has very detailed explanation.

1:  class Solution {  
2:  public:  
3:    ListNode *detectCycle(ListNode *head) {  
4:      ListNode *slow = head, *fast = head;  
5:      while (slow && fast) {  
6:        slow = slow->next;  
7:        if (fast->next == NULL) return NULL;  
8:        fast = fast->next->next;  
9:        if (slow == fast) break;  
10:      }  
11:      if (fast == NULL) return NULL;  
12:      fast = head;  
13:      while (slow != fast) {  
14:        slow = slow->next;  
15:        fast = fast->next;  
16:      }  
17:      return slow;  
18:    }  
19:  };