Linked List Cycle

Given a linked list, determine if it has a cycle in it.

Example

Given -21->10->4->5, tail connects to node index 1, return true

Challenge

Follow up:
Can you solve it without using extra space?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

/** * Definition of ListNode * class ListNode { * public: * int val; * ListNode *next; * ListNode(int val) { * this->val = val; * this->next = NULL; * } * } */ class Solution { public: /** * @param head: The first node of linked list. * @return: True if it has a cycle, or false */ bool hasCycle(ListNode *head) { // write your code here if (!head || !head->next) return false; ListNode *slow=head; ListNode *fast=head->next; while(fast && fast->next){ if (slow==fast) return true; slow=slow->next; fast=fast->next->next; } return false; } };

Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative.

Have you met this question in a real interview? 

Yes

Example

Given 1->2->3->4->5 and k = 2, return 4->5->1->2->3.

贴一个错的答案，没有考虑超过长度的问题。。。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    /**
     * @param head: the list
     * @param k: rotate to the right k places
     * @return: the list after rotation
     */
    ListNode *rotateRight(ListNode *head, int k) {
        // write your code here
        if (!head || !head->next)
            return head;
        ListNode dummy(0);
        dummy.next=head;
        head=&dummy;
        for(int i=0;i<k;i++){
            if (!head)
                return 0;  
            head=head->next;
        }
        ListNode* slow=&dummy;
        while(head->next){
            slow=slow->next;
            head=head->next;
        }
        ListNode* tmp=slow->next;
        slow->next=0;
        tmp->next=dummy.next;
        return tmp;
    }
};

这个解得测试结果：

Input

17->75->80->87->44->45->75->86->74->20->null, 19

Output

null

Expected

75->80->87->44->45->75->86->74->20->17->null

所以需要一个余数，先算个n，不过写了半天还是有bug，一怒之下换个思路，用环，先把首位相连，然后再重新断开。。。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    /**
     * @param head: the list
     * @param k: rotate to the right k places
     * @return: the list after rotation
     */
    ListNode *rotateRight(ListNode *head, int k) {
        // write your code here
        if(!head || !head->next)
            return head;
        int count=1;
        ListNode* runNode=head;
        while(runNode->next){
            count++;
            runNode=runNode->next;
        }
        runNode->next=head;
        runNode=head;
        for (int i=1; i<count-k%count; i++){
            runNode=runNode->next;
        }
        head=runNode->next;
        runNode->next=0;
        return head;
    }
};

Linked List Cycle II Show result

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Have you met this question in a real interview? 

Yes

Example

Given -21->10->4->5, tail connects to node index 1，返回10

Challenge

Follow up:
Can you solve it without using extra space?

这道题目今天刚听一个小师弟提起来，我refer他来面试，组里面他的人问他了这个题的变种，如何数出带环的linked list的长度。

他给出的答案是，在node里加一个flag, visited， 来检测，o(n)的时间和近似为无的空间复杂度，但是不是一个好的解，因为要改掉node 的定义。

问他组里那个人给的啥，他说告诉他用set存指针，一旦碰到collision就停止， 其实这个复杂度变成了o(n^3)的复杂度 1^2+2^2+3^2.。。有公式可以算的，另外加上额外的o(n)的空间开销。 我笑了好久，这真是个坑爹的解。 

师弟问我我怎么解，首先我说在允许额外空间的时候，不二法宝是hash table, 哈希来检测碰撞就可以把复杂度降到 o(n)，但是额外空间的开销还是o(n), 其实还要大些，背景hash table 还是会多出很大来做bucket.

然后我就跟他讲了有这么道题，不用额外空间求解。

快慢指针：

慢指针走一步，快指针走两步，

那么有环而相遇, 假设重叠位置为距离为A， 相遇距离重叠位置距离为B，继续走C到重叠

那么相遇的时候，快指针走了A+2B+C， 慢指针走了A+B,因为快指针是慢指针的两倍速度，所以

A+2B+C=2A+2B -> A=C。那么让头指针和慢指针继续走，直到相遇，就是他们的交错点，如果求长度，

记录头指针和慢指针的和为长

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

/** * Definition of ListNode * class ListNode { * public: * int val; * ListNode *next; * ListNode(int val) { * this->val = val; * this->next = NULL; * } * } */ class Solution { public: /** * @param head: The first node of linked list. * @return: The node where the cycle begins. * if there is no cycle, return null */ ListNode *detectCycle(ListNode *head) { // write your code here if(!head || !head->next) return 0; ListNode* slow=head->next; ListNode* fast= head->next->next; while(fast && fast->next){ if (slow==fast) break; slow=slow->next; fast=fast->next->next; } if (slow!=fast) return 0; while(head!=slow){ head=head->next; slow=slow->next; } return head; } };

Reverse Linked List II

Reverse a linked list from position m to n.

Have you met this question in a real interview? 

Yes

Example

Given 1->2->3->4->5->NULL, m = 2 and n = 4, return 1->4->3->2->5->NULL.

Note

Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.

Challenge

Reverse it in-place and in one-pass

/**
 * Definition of singly-linked-list:
 * 
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *        this->val = val;
 *        this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param head: The head of linked list.
     * @param m: The start position need to reverse.
     * @param n: The end position need to reverse.
     * @return: The new head of partial reversed linked list.
     */
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        // write your code here
        ListNode dummy(0);
        dummy.next=head;
        head=&dummy;
        for (int i=1; i<m; i++){
            if(head)
                head=head->next;
            else
                return 0;
        }
        
        ListNode* prev=0;
        ListNode* cur = head->next;
        ListNode* next = cur;
        for(int i=m; i<=n; i++){
            next=cur->next;
            cur->next=prev;
            prev=cur;
            cur=next;
        }
        head->next->next=cur;
        head->next = prev;
        return dummy.next;
    }
};

Sort List

Sort a linked list in O(n log n) time using constant space complexity.

Have you met this question in a real interview? 

Yes

Example

Given 1-3->2->null, sort it to 1->2->3->null.

大杂烩。。。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67

/** * Definition of ListNode * class ListNode { * public: * int val; * ListNode *next; * ListNode(int val) { * this->val = val; * this->next = NULL; * } * } */ class Solution { public: /** * @param head: The first node of linked list. * @return: You should return the head of the sorted linked list, using constant space complexity. */ ListNode *sortList(ListNode *head) { // write your code here if(!head ||!head->next) return head; ListNode *mid=findMiddle(head); ListNode *tmp=mid->next; mid->next=0; ListNode *left=sortList(head); ListNode *right=sortList(tmp); return mergeList(left,right); } ListNode* findMiddle(ListNode* head){ ListNode* slow=head; ListNode* fast=head->next; while(fast && fast->next){ slow=slow->next; fast=fast->next->next; } return slow; } ListNode* mergeList(ListNode* left, ListNode* right){ ListNode dummy(0); ListNode* head= &dummy; while(left && right){ if (left->val<right->val){ head->next=left; left=left->next; } else{ head->next=right; right=right->next; } head=head->next; } while(left){ head->next=left; head=head->next; left=left->next; } while(right){ head->next=right; head=head->next; right=right->next; } return dummy.next; } };

Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes' values.

Have you met this question in a real interview? 

Yes

Example

For example,
Given 1->2->3->4->null, reorder it to 1->4->2->3->null.

这题算是十八般武艺都用上了。。。

因为要reorder,所以要找到中间的位置，把中间以后的reverse,然后merge两个list...

算是linked list考察知识点比较全的了。。。

/** * Definition of ListNode * class ListNode { * public: * int val; * ListNode *next; * ListNode(int val) { * this->val = val; * this->next = NULL; * } * } */ class Solution { public: /** * @param head: The first node of linked list. * @return: void */ void reorderList(ListNode *head) { // write your code here if (!head ||!head->next) return; ListNode* mid=find_middle(head); ListNode* tmp = reverse(mid->next); mid->next=0; merge(head, tmp); } ListNode* find_middle(ListNode* head){ if (!head || !head->next) return head; ListNode* slow=head; ListNode* fast=head->next; while(fast && fast->next){ slow=slow->next; fast=fast->next->next; } return slow; } ListNode* reverse(ListNode* head){ ListNode* prev=0; while(head){ ListNode* tmp=head->next; head->next=prev; prev=head; head=tmp; } return prev; } void merge(ListNode* a, ListNode* b){ ListNode dummy(0); ListNode* head=&dummy; while(a && b){ head->next=a; a=a->next; head=head->next; head->next=b; b=b->next; head=head->next; } if (a) head->next=a; if (b) head->next=b; } };

Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list.

Analyze and describe its complexity.

Have you met this question in a real interview? 

Yes

Example

Given lists:

[
  2->4->null,
  null,
  -1->null
],

return -1->2->4->null.

如果是两个list 合并的话，比较一下大小，o(m+n)的时间复杂度， 但是如果合并k个数组的话，需要排序，实际上就变成了klgk *(m+n)了。。。如果借用heap的话，复杂度可以降到lgk(m+n)。。。

/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param lists: a list of ListNode
     * @return: The head of one sorted list.
     */
    struct compare{
        bool operator()(ListNode* left, ListNode* right){
            return left->val>right->val;
        };
    };
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        // write your code here
        priority_queue<ListNode*, vector<ListNode*>, compare> queue;
        ListNode dummy(0);
        ListNode* head=&dummy;
        for (int i=0; i<lists.size();i++){
            if (lists[i])
                queue.push(lists[i]);
        }
        while(!queue.empty()){
            ListNode* tmp=queue.top();
            queue.pop();
            if (tmp->next)
                queue.push(tmp->next);
            head->next=tmp;
            head=head->next;
        }
        if(head)
            head->next=0;
        return dummy.next;
    }
};

Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

和graph copy一样的，先用一个hash table存一下，先copy 边，再copy线。。。不二法门。。。

/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    /**
     * @param head: The head of linked list with a random pointer.
     * @return: A new head of a deep copy of the list.
     */
    RandomListNode *copyRandomList(RandomListNode *head) {
        // write your code here
        if (!head)
            return 0;
        unordered_map<RandomListNode*, RandomListNode*> map;
        RandomListNode* root=head;
        while(head){
            map[head]=new RandomListNode(head->label);
            head=head->next;
        }
        head=root;
        while(head){
            if (head->next)
                map[head]->next=map[head->next];
            if (head->random)
                map[head]->random= map[head->random];
            head=head->next;
        }
        return map[root];
    }
};

Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

Have you met this question in a real interview? 

Yes

Example

               2
1->2->3  =>   / \
             1   3

其实做过怎么把sorted array变成 binary tree就知道这个咋做了
回忆下array的做法

给个beg, end,求个中间数，那么中间数必然为root, 然后递归求左边subarrray和右边subarray的中间数，分别为其左右孩子，返回root.

那么对于linked list就不能那么任性的随便跳来跳去，必须严格遵循inorder的办法来遍历，这样才能实现o(n)的方法构筑，而且单链表跳来跳去也不可能。。。

所以trick在于，同样用beg, end来trace，但是要不停的update head. 因为是inorder,从左娃，中娃到又娃的时候head已经移到那里了。具体看代码

/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @return: a tree node
     */
    TreeNode *sortedListToBST(ListNode *head) {
        // write your code here
        int count=countList(head);
        return helper(head, 0, count-1);
    }
    
    TreeNode* helper(ListNode*& head, int beg, int end){
        if (!head || beg>end)
            return 0;
        int mid=beg+(end-beg)/2;
        TreeNode* left=helper(head, beg,mid-1);
        TreeNode* root= new TreeNode(head->val);
        head=head->next;
        TreeNode* right= helper(head, mid+1, end);
        root->left=left;
        root->right=right;
        return root;
    }
    
    int countList(ListNode* head){
        int count=0;
        while(head){
            count++;
            head=head->next;
        }
        return count;
    }
};

Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

Have you met this question in a real interview? 

Yes

Example

Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

Tags Expand  


就是个比较tricky的题目，画一画就是，永远去重复元素之前的为head,那么在循环里需要判断head->next && head->next->next 存在且数值相等，然后移除，否则遍历。 取巧的地方就是知道重复元素永远存在两个以上，所以不需要担心。。。。

/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution{
public:
    /**
     * @param head: The first node of linked list.
     * @return: head node
     */
    ListNode * deleteDuplicates(ListNode *head) {
        // write your code here
        ListNode dummy(0);
        dummy.next=head;
        head=&dummy;
        while(head){
            if (head->next && head->next->next && head->next->val ==head->next->next->val){
                int val=head->next->val;
                while(head->next && head->next->val==val){
                    ListNode* tmp=head->next;
                    head->next=tmp->next;
                    delete tmp;
                }
            } else{
                head=head->next;
            }
        }
        return dummy.next;
    }
};

Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2->null and x = 3,
return 1->2->2->4->3->5->null.

依旧是基础题，出错的地方是第二个指针next要设为0，错在这里了。。。dummy node的题目

/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @param x: an integer
     * @return: a ListNode 
     */
    ListNode *partition(ListNode *head, int x) {
        // write your code here
        ListNode dummyA(0);
        ListNode dummyB(0);
        ListNode* a= &dummyA;
        ListNode* b= &dummyB;
        while(head){
            if (head->val<x){
                a->next=head;
                a=a->next;
            } else{
                b->next=head;
                b=b->next;
            }
            head=head->next;
        }
        b->next=NULL;
        a->next=dummyB.next;
        return dummyA.next;
    }
};

Remove Nth Node From End of List

Given a linked list, remove the nth node from the end of list and return its head.

Have you met this question in a real interview? 

Yes

Example

Given linked list: 1->2->3->4->5->null, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5->null.

Note

The minimum number of nodes in list is n.

Challenge

O(n) time

一道基础题，不过用了两个linkedlist常用的技巧： dummy node和快慢指针 （算是吧。。。）

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

/** * Definition of ListNode * class ListNode { * public: * int val; * ListNode *next; * ListNode(int val) { * this->val = val; * this->next = NULL; * } * } */ class Solution { public: /** * @param head: The first node of linked list. * @param n: An integer. * @return: The head of linked list. */ ListNode *removeNthFromEnd(ListNode *head, int n) { // write your code here ListNode dummy(0); dummy.next=head; head=&dummy; for (int i=0; i<n; i++){ if (!head->next) return 0; head=head->next; } ListNode* prev=&dummy; while(head->next){ prev=prev->next; head=head->next; } ListNode* tmp= prev->next; prev->next= prev->next->next; delete tmp; return dummy.next } };