数据结构与算法

学习数据结构与算法资源

《算法导论》- Cormen,T.H.

算法可视化项目

topcoder

leetcode

coursera

以下题目均来自leetcode

翻转链表

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

/**
 * 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* prev = NULL;
        ListNode* curr = head;
        ListNode* next = NULL;
        
        while (curr) {
            next = curr->next;//备份当前节点的下一个节点

            curr->next = prev;//更新当前节点

            prev = curr;//当前节点保留为下一个节点的前节点

            curr = next;//当前节点移动到下一个节点

        }
        
        return prev;
    }
};

void test206(){
    ListNode a;
    a.value  = 10;
    
    ListNode b;
    b.value  = 20;
    
    ListNode c;
    c.value  = 30;
    
    ListNode d;
    d.value  = 40;
    
    ListNode e;
    e.value  = 50;
    
    a.next = &b;
    b.next = &c;
    c.next = &d;
    d.next = &e;
    e.next = NULL;
    
    Solution206 s;
    ListNode* result = s.reverseList(&a);
    
    ListNode *head = result;
    while(head){
        cout << head->value << endl;
        head = head->next;
    }
}

翻转链表

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明: 1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        int change_len = n - m + 1;//反转的个数

        ListNode* pre_head = NULL;

        ListNode* result = head;

        while(head && --m){ //找到反转的开始位置

            pre_head = head;//反转区间第一个节点的前节点

            head = head->next;
        }

        
        ListNode *reverse_tail = head;//反转后的尾节点

        ListNode *new_head = NULL;
        
        while(head && change_len){//开始反转

            ListNode* next = head->next;

            head->next = new_head;

            new_head = head;

            head = next;

            change_len--;

        }
        
        //反转后的尾节点的下一个节点 为剩余节点的头结点

        reverse_tail->next = head;
       
        if(pre_head){ //不是从第一个节点开始反转

          pre_head->next = new_head;
        }else{
          result = new_head;//new_head为反转后的头

        }
        return result;
    }
};

相交链表

编写一个程序，找到两个单链表相交的起始节点。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        map<ListNode*, bool> vis;
        while(headA != NULL){
        	vis[headA] = true;
        	headA = headA->next;
        }
        while(headB != NULL){
        	if(vis[headB]) return headB;
        	vis[headB] = true;
        	headB = headB->next;
        }
        return NULL;
    }
};


class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        set<ListNode*> vis;
        while(headA != NULL){
        	vis.insert(headA);
        	headA = headA->next;
        }
        while(headB != NULL){
        	if(vis.find(headB) != vis.end()) return headB;
        	headB = headB->next;
        }
        return NULL;
    }
};

class Solution {
public:
    int getListLength(ListNode* head){
        int length = 0;
        while(head != NULL){
            length++;
            head = head->next;
        }
        return length;
    }

    ListNode* forwardList(int longLength,int shortLength,ListNode* head){
        int move = longLength - shortLength;
        while(head && move){
            head = head->next;
            move--;
        }
        return head;
    }

    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int aLength = getListLength(headA);
        int bLength = getListLength(headB);
        if(aLength>bLength){
            headA = forwardList(aLength,bLength,headA);
        }else{
            headB = forwardList(bLength,aLength,headB);
        }
        while(headA&&headB){
            if(headA == headB){return headA;}
            headA = headA->next;
            headB = headB->next;
        }
        return NULL;
    }
};

链表求环

给定一个链表，判断链表中是否有环。

class Solution {
public:
    bool hasCycle(ListNode *head) {
        set<ListNode*> list;
        while(NULL != head){
            if(list.count(head))
                return true;
            else
                list.insert(head);
            head = head->next;
        }
        return false;
    }
};

class Solution {
public:
    ListNode* detectCycle(ListNode *head) {
        set<ListNode*> list;
        while(NULL != head){
            if(list.find(head) != list.end())
                return head;
            else
                list.insert(head);
            head = head->next;
        }
        return NULL;
    }
};

//快慢指针，慢的跑一个节点，快的跑二个节点，相遇在meet节点。然后再从head与meet出发相同出发，相遇后就是环的起点。

class Solution {
public:
    ListNode* detectCycle(ListNode *head) {
        ListNode *fast = head;
        ListNode *slow = head;
        ListNode *meet = NULL;
        while(fast){
            slow = slow->next;
            fast = fast->next;
            if(fast == NULL){
                return NULL;
            }
            fast = fast->next;
            if(fast == slow){
                meet = fast;
                break;
            }
        }
        while(head && meet){
            if(head == meet){return head;}
            head = head->next;
            meet = meet->next;
        }
        return NULL;
    }
};

链表划分

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例:

输入: head = 1->4->3->2->5->2, x = 3 输出: 1->2->2->4->3->5

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode less_head(0);
        ListNode more_head(0);
        ListNode *less_ptr = &less_head;
        ListNode *more_ptr = &more_head;
        while(head){
            if(head->val < x){
                less_ptr->next = head;
                less_ptr = head;
            }else{
                more_ptr->next = head;
                more_ptr = head;
            }  
            head = head->next;
        }
        less_ptr->next = more_head.next;
        more_ptr->next = NULL;
        return less_head.next;
    }
};

链表拷贝

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。

要求返回这个链表的深拷贝。

// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node() {}

    Node(int _val, Node* _next, Node* _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};

class Solution {
public:
    Node* copyRandomList(Node* head) {
        map<node*,int> node_map;
        vector<node*> node_vec;
        Node* ptr = head;
        int  i = 0;
        while(ptr){
            node_vec.push_back(new Node(ptr->val));
            node_map[ptr] = i;
            ptr = ptr->next;
            i++;
        }
        node_vec.push_back(0);
        ptr = head;
        i = 0;
        while(ptr){
            node_vec[i]->next = node[i+1];
            if(ptr->random){
                int id = node_map[ptr->random];
                node_vec[i]->random = node_vec[id];
            }
            pr = ptr->next;
            i++;
        }
        return node_vec[0];
    }
};

链表合并

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4

/**
 * 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) {
        if(l1==NULL)
            return l2;
        if(l2==NULL)
            return l1;
        if(l1->val < l2->val){
            l1->next = mergeTwoLists(l1->next,l2);
            return l1;
        }else{
            l2->next = mergeTwoLists(l1,l2->next);
            return l2;
        }
    }
};

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
       ListNode temp_head(0);
       ListNode *pre = &temp_head;
       while(l1 && l2){
           if(l1->val < l2->val){
               pre->next = l1;
               l1 = l1->next;
           }else{
               pre->next = l2;
               l2 = l2->next;
           }
            pre = pre->next;
       }
       if(l1){
           pre->next = l1;
       }
       if(l2){
           pre->next = l2;
       }
       return temp_head.next;
    }
};

链表合并

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3->4->4->5->6

class Solution {
public:
    
    bool compare(const ListNode *a,const ListNode* b){
        return a->val < b->val;
    }
    
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        vector<ListNode*> node_vec;
        for(int i = 0;i<lists.size();i++){
            LinkNode* head = list[i];
            while(head){
                node_vec.push_back(head);
                head = head->next;
            }
        }
        int length = node_vec.size();
        if(length == 0)
        {
            return NULL;
        }
        std:sort(node_vec:begin(),node_vec:end(),compare);
        for(int i = 1;i<length;i++){
            node_vec[i-1].next = node_vec[i];
        }
        node_vec[length-1].next =  NULL;
        return node_vec[0]; 
    }
};

class Solution {
public:
    
    
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.empty()){
            return NULL;
        }
        if(lists.size()==1){
            return lists[0];
        }
        if(lists.size()==2){
            return mergeTwoLists(lists[0],lists[1]);
        }
        int mid = lists.size()/2;
        vector<ListNode*> sub_list1;
        vector<ListNode*> sub_list2;
        for(int i = 0;i<mid;i++){
            sub_list1.push_back(lists[i]);
        }
        for(int i = mid;i<lists.size();i++){
            sub_list2.push_back(lists[i]);
        }
         ListNode* l1 = mergeKLists(sub_list1);
         ListNode* l2 = mergeKLists(sub_list2);
        return  mergeTwoLists(l1,l2);
    }
};

链表

学习数据结构与算法资源

翻转链表

翻转链表

相交链表

链表求环

链表划分

链表拷贝

链表合并

链表合并

CATALOG

FEATURED TAGS

FRIENDS