STL系列——list

template < class T, class Alloc = allocator<T> > class list;
list是一个序列容器,是以双端链表的形式实现的。list相对于其他序列容器,在任意位置的删除、移动、提取元素的性能更好,但是在随机访问上的性能表现比较差。

Member functions

default (1)	list();
                explicit list (const allocator_type& alloc);
fill (2)	explicit list (size_type n, const allocator_type& alloc = allocator_type());
                list (size_type n, const value_type& val,const allocator_type& alloc = allocator_type());
range (3)	template <class InputIterator>
                    list (InputIterator first, InputIterator last,const allocator_type& alloc = allocator_type());
copy (4)	list (const list& x);
                list (const list& x, const allocator_type& alloc);
move (5)	list (list&& x);
                list (list&& x, const allocator_type& alloc);
initializer list (6)
                list (initializer_list<value_type> il,const allocator_type& alloc = allocator_type());
copy (1)	list& operator= (const list& x);
move (2)	list& operator= (list&& x);
initializer list (3)
                list& operator= (initializer_list<value_type> il);

用法:

std::list<int> first (3);      // list of 3 zero-initialized ints
std::list<int> second (5);     // list of 5 zero-initialized ints
second = first;
first = std::list<int>();

Iterators

begin(), end(), rbegin(), rend(), cbegin(), cend(), crbegin(), crend()
当容器为空时,begin() 返回的迭代器不能解引用,end( )和begin( )返回一样。

Capacity

bool empty() const noexcept;              // 判断是否为空
size_type size() const noexcept;          // list中元素个数
size_type max_size() const noexcept;

Element access

std::list::front( )

 reference front();
const_reference front() const;

std::list::back( )

reference back();
const_reference back() const;

Modifiers

 

Merge k Sorted Lists

问题描述:
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
分而治之的思想:   404ms

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.empty())
            return NULL;
        return dac(lists,0,lists.size()-1);
    }
private:
    ListNode* dac(vector<ListNode*>& lists,int low,int high)
    {
        int mid=(low+high)/2;
        if(low==high)
            return lists[low];
        ListNode* l1=dac(lists,low,mid);
        ListNode* l2=dac(lists,mid+1,high);
        return mergeTwoLists(l1,l2);
    }
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(!l1)
            return l2;
        if(!l2)
            return l1;
        if(l1->val<l2->val)
            l1->next=mergeTwoLists(l1->next,l2);
        else
            l2->next=mergeTwoLists(l1,l2->next);
    }
};

使用优先队列priority_queue找到最小的元素   436ms

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
struct cmp{
    bool operator()(const ListNode* l, const ListNode* r){
        return l->val > r->val;
    }
};
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, cmp> q;
        for(auto l : lists){
            if(l) q.push(l);
        }
        if(q.empty())
            return NULL;
        ListNode* result = q.top();      // head
        q.pop();
        if(result->next)
            q.push(result->next);
        ListNode* pointer = result;
        while(!q.empty()){
            pointer->next = q.top();      // the min
            q.pop();
            pointer = pointer->next;
            if(pointer->next)             // the responding ListNode* is not empty
                q.push(pointer->next);
        }
        return result;
    }
};

使用make_heap 480ms

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
//struct cmp{
//   bool operator()(const ListNode* l, const ListNode* r){
//        return l->val > r->val;
//    }
//};
bool cmp(const ListNode* l, const ListNode* r){
    return l->val > r->val;
}
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
       ListNode head(0);
       ListNode *curr = &head;
       vector<ListNode*> v;
        for(auto l : lists){
            if(l) v.push_back(l);
        }
        make_heap(v.begin(), v.end(), cmp);
        while(v.size()>0){
            curr->next = v.front();      // the min
            pop_heap(v.begin(), v.end(), cmp);
            v.pop_back();
            curr = curr->next;
            if(curr->next){             // the responding ListNode* is not empty
                v.push_back(curr->next);
                make_heap(v.begin(), v.end(), cmp);
            }
        }
        return head.next;
    }
};

 

Merge Two Sorted Lists

ListNode* MergeSort(ListNode *left, ListNode*right){
        ListNode* newNode = new ListNode(0);                             //
        ListNode* p = newNode;
        while(left != NULL && right != NULL){
            if(left->val <= right->val){
                p->next = left;
                p = p->next;
                left = left->next;
            }else{
                p->next = right;
                p = p->next;
                right = right->next;
            }
        }
        if(left != NULL)
            p->next = left;
        if(right != NULL)
            p->next = right;
        return newNode->next;
    }

延伸:
在两个有序链表中查找第K大元素。 思路:和有序链表合并思路一样,不过在合并过程中需添加计数,同时需要注意相同大小元素只记1次。

Sort List

问题描述:

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

解决代码:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(head == NULL || head->next == NULL)
            return head;
        ListNode *first = head, *second = head->next, *mid= NULL;
        while(second->next != NULL && second->next->next != NULL){       // find the mid position
            first = first->next;
            second = second->next->next;
        }
        mid = first->next;
        first->next = NULL;
        ListNode *left = sortList(head);
        ListNode *right = sortList(mid);
        return MergeSort(left, right);
    }
    ListNode* MergeSort(ListNode *left, ListNode*right){
        ListNode* newNode = new ListNode(0);                             //
        ListNode* p = newNode;
        while(left != NULL && right != NULL){
            if(left->val <= right->val){
                p->next = left;
                p = p->next;
                left = left->next;
            }else{
                p->next = right;
                p = p->next;
                right = right->next;
            }
        }
        if(left != NULL)
            p->next = left;
        if(right != NULL)
            p->next = right;
        return newNode->next;
    }
};

有人采取自底向上的策略,给出了非递归解法,时间O(nlgn) 空间O(1):

/**
 * Merge sort use bottom-up policy,
 * so Space Complexity is O(1)
 * Time Complexity is O(NlgN)
 * stable sort
*/
class Solution {
public:
    ListNode *sortList(ListNode *head) {
        if(!head || !(head->next)) return head;
        //get the linked list's length
        ListNode* cur = head;
        int length = 0;
        while(cur){
            length++;
            cur = cur->next;
        }
        ListNode dummy(0);
        dummy.next = head;
        ListNode *left, *right, *tail;
        for(int step = 1; step < length; step <<= 1){
            cur = dummy.next;
            tail = &dummy;
            while(cur){
                left = cur;
                right = split(left, step);
                cur = split(right,step);
                tail = merge(left, right, tail);
            }
        }
        return dummy.next;
    }
private:
    /**
     * Divide the linked list into two lists,
     * while the first list contains first n ndoes
     * return the second list's head
     */
    ListNode* split(ListNode *head, int n){
        //if(!head) return NULL;
        for(int i = 1; head && i < n; i++) head = head->next;
        if(!head) return NULL;
        ListNode *second = head->next;
        head->next = NULL;
        return second;
    }
    /**
      * merge the two sorted linked list l1 and l2,
      * then append the merged sorted linked list to the node head
      * return the tail of the merged sorted linked list
     */
    ListNode* merge(ListNode* l1, ListNode* l2, ListNode* head){
        ListNode *cur = head;
        while(l1 && l2){
            if(l1->val > l2->val){
                cur->next = l2;
                cur = l2;
                l2 = l2->next;
            }
            else{
                cur->next = l1;
                cur = l1;
                l1 = l1->next;
            }
        }
        cur->next = (l1 ? l1 : l2);
        while(cur->next) cur = cur->next;
        return cur;
    }
};

https://leetcode.com/discuss/28594/bottom-recurring-with-space-complextity-time-complextity

单链表反转

题目:反转一个单链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *reverseHead = NULL;
        ListNode *node = head;
        ListNode *pre= NULL;
        while(node != NULL)
        {
            ListNode *next = node->next;
            if(next == NULL)
                reverseHead = node;
            node->next = pre;
            pre = node;
            node = next;
        }
        return reverseHead;
/** another version
        if(!pHead)
            return pHead;
        
        ListNode* curr = pHead;
        ListNode* prev = NULL;
        ListNode* next;
        while(curr->next){
            next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        
        curr->next = prev;
        return curr;
*/
    }
};

逆序输出单链表

void PrintReverseLink(ListNode *head)
{
    if(head->next != NULL){
       PrintReverseLink(head->next);
       printf("%d ",head->next->val);
    }
}

 

ListNode *reverse(ListNode *p, ListNode* &head)
{
   if(p == NULL || p->next == NULL)
   {
      head = p;
      return p;
    }
    else
    {
      ListNode *data = reverse(p->next, head);
      data->next = p;
      return data;
    }
}