暴风影音2014校招笔试题

1、合并两个已经排序的单链表为一个排序的单链表，相同内容只保留一个如：单链表a:1->2->3->4 单链表b:3->4->5 输出：1->2->3->4->5

#include <iostream>
    #include <climits>
    using namespace std;

    struct ListNode{
        int val;
        ListNode *next;
        ListNode(int x):val(x),next(NULL){}
    };
    //
    ListNode* MergeSortedList(ListNode *list1,ListNode *list2){
        // 头节点
        ListNode *head = new ListNode(-1);
        ListNode *p = head;
        int val1,val2;
        // 合并
        while(list1 != NULL || list2 != NULL){
            val1 = (list1 == NULL) ? INT_MAX : list1->val;
            val2 = (list2 == NULL) ? INT_MAX : list2->val;
            // 相同内容只保留一个
            if(val1 == val2){
                p->next = list1;
                list1 = list1->next;
                list2 = list2->next;
            }//if
            // 当前链表1小
            else if(val1 < val2){
                p->next = list1;
                list1 = list1->next;
            }
            // 当前链表2小
            else{
                p->next = list2;
                list2 = list2->next;
            }
            p = p->next;
        }//while
        return head->next;
    }

    int main() {
        int A[] = {1,2,4,7,9};
        int B[] = {1,3,4,8,9,11,12};
        // 链表1
        ListNode *head1 = new ListNode(A[0]);
        ListNode *p1 = head1;
        for(int i = 1;i < 5;i++){
            ListNode *node = new ListNode(A[i]);
            p1->next = node;
            p1 = node;
        }//for
        // 链表2
        ListNode *head2 = new ListNode(B[0]);
        ListNode *p2 = head2;
        for(int i = 1;i < 7;i++){
            ListNode *node = new ListNode(B[i]);
            p2->next = node;
            p2 = node;
        }//for
        ListNode *head = MergeSortedList(head1,head2);
        // 输出
        ListNode *p = head;
        while(p){
            cout<<p->val<<" ";
            p = p->next;
        }//while
        cout<<endl;
    }

2、编写程序，在原字符串中把尾部m个字符移动到字符串的头部，要求：长度为n字符串操作时间复杂度为O(n),时间复杂度为O(1)。
如：原字符串为”Ilovebaofeng”，m=7，输出结果：”baofengIlove”。

3、暴风影音的片源服务器上保存着两个文件a和b，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让你找出a,b文件共同的URL。要求：算法设计。