LeetCode题目:Convert Sorted List to Binary Search Tree

问题比上一个难一点,如果是可以用O(n)空间的话,倒是可以开一个数组放上这n个数,然后按上一个问题的解法去做。总体时间O(n),空间O(n)。

不过这题这样出应该不是这个意思。假如不用O(n)空间的话:
可以先数一下一共有多少个节点。O(n)时间。
然后去找到根节点(数数),然后根节点之前是左子树,之后是右子树,并且两个子树的节点个数都是可以直接计算出来的,递归解这个问题就可以了。
那么总体时间复杂度是O(n*logn),空间O(logn)



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.



代码:114ms过大集合

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    TreeNode *formTree(ListNode *head, int count) {
        if(count <= 0) return NULL;
        int rootIndex = count / 2;
        ListNode *rootNode = head;
        for(int ir = 0; ir < rootIndex; ++ir) {
            rootNode = rootNode->next;
        }
        TreeNode *root = new TreeNode(rootNode->val);
        root->left = formTree(head,rootIndex);
        root->right = formTree(rootNode->next, count - rootIndex - 1);
        return root;
    }
public:
    TreeNode *sortedListToBST(ListNode *head) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        //1. find the node count, takes O(n) time
        int nodeCount = 0;
        for(ListNode *cur = head; cur != NULL; cur = cur->next) {
            ++nodeCount;
        }
        
        //2. form the tree with the middle as the root
        return formTree(head, nodeCount);
    }
};

CCI题目2-5:Find Loop

建一个hash来做,从前往后扫描,遇到重复的输出就可以了。(findLoop)
最后有c++中map的简单实用例子。



另外cci上写了一个更有意思的算法,就是两个指针在链表上跑,一个快一个慢,慢的跑一步,快的跑两步。
当他们相遇的时候,让快的那个到链表开头,然后两个指针以相等的速度(一比一),继续跑,再次相遇的时候就是loop的开始点。

为什么?
假设有一个n米长的环形跑道,两个人一快一慢(2:1)从同一个起点开跑。下次相遇在哪儿?起点,而且是快的跑了两圈,慢的一圈。
进一步,如果快的那个先跑了k米呢?那他们应该相遇在距起点k米的位置。因为Sl = t, Sh = 2t + k,而令Sh = Sl + pn,可以得到t = pn – k。也就是他们总会在这个位置相遇。
所以此时让快的那个回到起点,(起点正好距循环开始k米),下次相遇,就是循环开始点。
这个想法很巧(findLoopEx)



题目
Given a circular linked list, implement an algorithm which returns node at the begin- ning of the loop.
DEFINITION
Circular linked list: A (corrupt) linked list in which a node’s next pointer points to an earlier node, so as to make a loop in the linked list.
EXAMPLE
input: A -> B -> C -> D -> E -> C [the same C as earlier]
output: C



代码

<

pre>
Node * findLoop(Node *pHead) {
map exmap;
while (pHead) {
if (exmap.find(pHead) != exmap.end()) {
return pHead;
}
exmap[pHead] = true;
pHead = pHead->next;
}
return NULL;
}

Node *findLoopEx(Node *pHead) {
Node *pRunner = pHead;
Node *pWalker = pHead;
int step = 0;

//each step of walker, runner goes two.
while (pRunner) {
    pRunner = pRunner->next;
    if (++step == 2) {
        pWalker = pWalker->next;
        step = 0;
        if (pRunner == pWalker) {
            break;
        }
    }
}
if (!pRunner) {
    return NULL;//no loop
}
//then they meet at the k posotion before loop started
//and the k is nodes before loop start
//so let runner back to head and with speed of 1
//they go simutaniously, when next meet, that position is the loop start point
pRunner = pHead;
while (pWalker) {
    if (pWalker == pRunner) {
        return pWalker;
    }
    pWalker = pWalker->next;
    pRunner = pRunner->next;
}
return NULL;//something wrong

}

int main(int argc, const char * argv[])
{
cout<<“Hello\n”;
Node *phead = loopList(10, 8);
printList(phead);
cout<<“process…”<<endl;
Node *pLoop = findLoop(phead);
printList(pLoop);
cout<<“done”<<endl;
return 0;
}



map操作

void mapTest(){
    map testmap;
    //insert key,val in map:
    testmap[1] = true;
    testmap[666] = false;
    //find key in map
    map::iterator it = testmap.find(1);
    if (it != testmap.end()) {
        //key if found in map
        int key = it->first;//this is key
        bool val = it->second;//this is val;
        it->second = !val;
    }
    //delete a key
    testmap.erase(1);
}

CCI题目2-3:Remove Node at Middle of a Link List

两个指针,一个在前面跑,一个跟在后面,前面的跑两步,后面的跑一步。最后删除后面指针指向的那个节点即可。



题目
Implement an algorithm to delete a node in the middle of a single linked list, given only access to that node.
EXAMPLE
Input: the node ‘c’ from the linked list a->b->c->d->e
Result: nothing is returned, but the new linked list looks like a->b->d->e



代码

<

pre>
void RemoveMiddle(Node **ppHead) {
//1,2 del 0; 3,4 del 1; …
if (!(ppHead)) {
return;
}
Node *pRunner = (
ppHead)->next;
Node **ppPre = ppHead;
bool move = false;
while (pRunner) {
pRunner = pRunner->next;
if (move) {
ppPre = &(*ppPre)->next;
}
move = !move;
}
//hold the removing one
pRunner = *ppPre;
//delete it from list
*ppPre = pRunner->next;
//delete it
delete pRunner;
}

int main(int argc, const char * argv[])
{
cout<<“Hello\n”;
string instr;
// instr = “1,2,3,4,5,6,7”;
// instr = “1,2,2,2,2,2,2,1”;
// instr = “1,1,1,1,1,1,1,1,1”;
// instr = “10,9,8,7,6,5,4,3,2,1,0”;
// instr = “0,1,2,3,4,5,6,7,8,9,10”;
instr = “”;
// cin>>instr;
Node *phead = strToList(instr);
printList(phead);
cout<<“process…”<<endl;
RemoveMiddle(&phead);
printList(phead);
cout<<“done”<<endl;
return 0;
}

CCI习题2-2:nTh From the last

画一个链表出来,实际看看就知道怎么写了。
用一个pointer pRun在前面从pHead先跑n个位置。(如果中途为NULL,说明输入的数大于了链表长度)
然后用另一个pointer pCur从pHead开始,和pRun同步往后跑,直到pRun为NULL,这个时候返回pCur就可以了。



题目
Implement an algorithm to find the nth to last element of a singly linked list.



代码,只贴主要部分,用到的其它辅助函数和Node结构参见2-1

<

pre>
//zero based n th from the rear
Node * nThFromLast(Node *pHead, int n) {
if (n < 0) {
cout<<“n below 0″<<endl;
return NULL;
}
Node *pCur = pHead;
Node *pRun = pHead;
//1.let pRun go n position before pCur
for (int i = 0; i <= n; ++i) {
if (!pRun) {
cout<<“Not enough nodes”<<endl;
return NULL;//no enough nodes in the link list
}
pRun = pRun->next;
}
//2.go paralell untile pRun become NULL
while (pRun) {
pRun = pRun->next;
pCur = pCur->next;
}
return pCur;
}
int main(int argc, const char * argv[])
{
cout<<“Hello\n”;
string instr;
// instr = “1,2,3,4,5,6,7”;
// instr = “1,2,2,2,2,2,2,1”;
// instr = “1,1,1,1,1,1,1,1,1”;
instr = “10,9,8,7,6,5,4,3,2,1,0”;
// cin>>instr;
Node *phead = strToList(instr);
printList(phead);
cout<<“process…”<<endl;
Node *pNth = nThFromLast(phead,10);//test 10,9,5,1,0,12,-11
if (pNth) {
cout<value<<endl;
}
cout<<“done”<<endl;
return 0;
}

CCI习题2-1: Remove Duplicates

如果可用缓存的话,可以建一个hashtable,然后track每一个值有没有出现过;
否则的话,只能O(n2)去跑了(见下面代码)



Remove Duplicates
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?

<br>
代码

<

pre>
//
// main.cpp
// CCI.2.1.RemoveDuplicate
//
// Created by Qiu Xiangyu on 12-11-14.
// Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

include

include

using namespace std;
struct Node{
int value;
Node *next;
Node(int val):value(val),next(NULL) {;}
};
Node *strToList(string str){
Node *phead = NULL;
Node **ppnext = &phead;
int v = 0;
bool rem = false;
for (int i = 0; i < str.size(); ++i) {
char c = str[i];
if (c >= ‘0’ && c <= ‘9’) {
v = 10 * v + (c – ‘0’);
rem = true;
} else {
*ppnext = new Node(v);
ppnext = &((*ppnext)->next);
v = 0;
rem = false;
}
}
if (rem) {
*ppnext = new Node(v);
}
return phead;
}
void printList(Node *phead) {
cout<<“List : “;
while (phead) {
cout<value;
if (phead->next) {
cout<<“,”;
}
phead = phead->next;
}
cout<<endl;
}

void removeDuplicate(Node *pHead) {
Node *pCur = pHead;
while (pCur) {
Node **ppNext = &pCur->next;
while (*ppNext) {
Node *pNext = *ppNext;
if (pNext->value == pCur->value) {
*ppNext = pNext->next;
delete pNext;
pNext = NULL;
} else {
ppNext = &(*ppNext)->next;
}
}
pCur = pCur->next;
}
}

int main(int argc, const char * argv[])
{
cout<<“Hello\n”;
string instr;
// instr = “1,2,3,4,5,6,7”;
instr = “1,2,2,2,2,2,2,1”;
// instr = “1,1,1,1,1,1,1,1,1”;
// cin>>instr;
Node *phead = strToList(instr);
printList(phead);
cout<<“process…”<<endl;
removeDuplicate(phead);
printList(phead);
cout<<“done”<<endl;
return 0;
}

LeetCode题目:Swap Nodes in Pairs

题目简单,就是每次将两个非空节点swap,然后移动两个位置继续,直到无法找到两个非空节点为止。



Swap Nodes in Pairs
Given a linked list, swap every two adjacent nodes and return its head.
For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.
Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.



代码:16ms过大集合

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *swapPairs(ListNode *head) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        ListNode **ppre = &head;
        
        while(true) {
            ListNode *n0 = *ppre;
            if(NULL == n0) return head;
            ListNode *n1 = n0->next;
            if(NULL == n1) return head;
            
            //swap n0 and n1
            *ppre = n1;
            n0->next = n1->next;
            n1->next = n0;
            ListNode *next = n1->next;
            ppre = &(n0->next);
        }
        
        return head;
    }
};

LeetCode题目:Remove Duplicates from Sorted List II

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.
For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.



代码:44ms过大集合

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        ListNode *root = NULL;
        ListNode **ppNext = &root;
        while(head) {
            if(head->next == NULL || head->next->val != head->val) {
                *ppNext = head;
                ppNext = &(head->next);
                head = head->next;
            } else {
                int val = head->val;
                do {
                    head = head->next;
                } while(head != NULL && head->val == val);
            }
        }
        *ppNext = NULL;
        return root;
    }
};

LeetCode题目:Remove Duplicates from Sorted List

简单,链表的问题注意收尾。



Remove Duplicates from Sorted List
Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.



代码:84ms过大集合

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(!head) return NULL;
        ListNode *last = head;
        ListNode *cur = last->next;
        while(cur) {
            if(cur->val != last->val) {
                last->next = cur;
                last = cur;
            }
            cur = cur->next;
        }
        last->next = NULL;
        return head;
    }
};

LeetCode题目:Partition List

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 and x = 3,
return 1->2->2->4->3->5.



逐个取head,判断之后加入左或者右边列表,最后合并两个列表,将最后一个元素的next置为NULL。



代码简单,就是注意要让最后那个node的next置为NULL。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *partition(ListNode *head, int x) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        ListNode *pL = NULL, *pR = NULL;
        ListNode *pLastR = NULL;
        ListNode **ppL = &pL, **ppR = &pR;
        while(head) {
            if(head->val < x) {
                //go to left
                *ppL = head;
                ppL = &(head->next);
            } else {
                //go to right
                *ppR = head;
                pLastR = head;
                ppR = &(head->next);
            }
            
            head = head->next;
        }
        //link left with right
        *ppL = pR;
        if(pLastR) pLastR->next = NULL;
        return pL;
    }
};

LeetCode题目:Merge Two Sorted Lists

Merge Two Sorted Lists
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.



代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode *proot = NULL;
        ListNode **pplast = &proot;
        while(l1 || l2){
            if(l1) {
                ListNode *minNode;
                if(!l2 || l1->val <= l2->val){
                    //l1 is min
                    minNode = l1;
                    l1 = l1->next;
                } else if(l2) {
                    //l2 is min
                    minNode = l2;
                    l2 = l2->next;
                }
                //proceed root
                *pplast = minNode;
                pplast = &(minNode->next);
            } else {
                //l1 is empty
                *pplast = l2;
                break;
            }
        }
        return proot;
    }
};

Leetcode题目:Add Two Numbers, 两个链表数相加

临睡前A一道题,题目简单,没什么可说的。就是需要小心对NULL指针的调用。



Add Two Numbers
You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        ListNode rootNode(0);
        ListNode *pCurNode = &rootNode;
        int forward = 0;
        while(l1||l2)
        {
            int v1 = (l1 ? l1->val : 0);
            int v2 = (l2 ? l2->val : 0);
            int sum = v1 + v2 + forward;
            forward = sum / 10;
            sum = sum % 10;
            ListNode *pNode = new ListNode(sum);
            pCurNode->next = pNode;
            pCurNode = pNode;
            if(l1) l1 = l1->next;
            if(l2) l2 = l2 ->next;
        }
        if(forward > 0)
        {
            ListNode *pNode = new ListNode(forward);
            pCurNode->next = pNode;
        }
        return rootNode.next;
    }
};

Code rewrite at 2012-12-26, Simpler

class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        int overflow = 0;
        ListNode *ret = NULL;
        ListNode **pnode = &ret;
        while(l1 && l2) {
            int val = l1->val + l2->val + overflow;
            overflow = val / 10;
            *pnode = new ListNode(val % 10);
            pnode = &((*pnode)->next);
            l1 = l1->next;
            l2 = l2->next;
        }
        ListNode *lremain = l1 ? l1 : l2;
        while(lremain) {
            int val = lremain->val + overflow;
            overflow = val / 10;
            *pnode = new ListNode(val % 10);
            pnode = &((*pnode)->next);
            lremain = lremain->next;
        }
        if(overflow > 0) {
            *pnode = new ListNode(overflow);
        }
        return ret;
    }
};

New C solution at 2016-04-22

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    if(l1 == NULL) return l2;
    if(l2 == NULL) return l1;
    struct ListNode* root = NULL;
    struct ListNode** next = NULL;
    int overflow = 0;
    while(l1 || l2 || overflow > 0){
        // calculation
        int v = overflow;
        if(l1){ v += l1->val; l1 = l1->next;}
        if(l2){ v += l2->val; l2 = l2->next;}
        overflow = v / 10;
        v = v % 10;
        // new node
        struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
        newNode->val = v;
        newNode->next = NULL;
        if(next) *next = newNode;
        next = &(newNode->next);
        if(root == NULL) root = newNode;
    }
    return root;
}

New Ruby solution at 2016-04-22

# Definition for singly-linked list.
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val)
#         @val = val
#         @next = nil
#     end
# end

# @param {ListNode} l1
# @param {ListNode} l2
# @return {ListNode}
def add_two_numbers(l1, l2)
    return l1 if l2.nil?
    return l2 if l1.nil?
    root = nil
    tail = nil
    overflow = 0
    while l1 || l2 || overflow > 0 do
        v = overflow
        unless l1.nil?
            v += l1.val
            l1 = l1.next
        end
        unless l2.nil?
            v += l2.val
            l2 = l2.next
        end
        overflow = v / 10
        v = v % 10
        new_node = ListNode.new(v)
        root = new_node if root.nil?
        tail.next = new_node unless tail.nil?
        tail = new_node
    end
    root
end