Algo_5_LinkedList

code c++ algo

學習算法

Leetcode 206

  • 用指針維護
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* next = nullptr;
        ListNode* cur = head;
        while(cur){
            next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
};

Leetcode 21

  • 使用dummy代替直接操作head，在刪除或變更節點的時候更方便
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* dummy,*temp;
        dummy = new ListNode();
        temp = dummy;
        while(list1 && list2){
            if(list1->val < list2->val){
                temp->next = list1;
                list1 = list1->next;
            }else{
                temp->next = list2;
                list2 = list2->next;
            }
            temp = temp->next;
        }
        if(list1) temp->next = list1;
        if(list2) temp->next = list2;
 
        return dummy->next;
    }
};

Leetcode 141

  • 當行成cycle時，一定會讓雙指針只到相同的地方
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast && fast->next){
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast){
                return true;
            }
        }
        return false;
    }
};

Leetcode 19

  • 先讓head移動到指定的n節點，接著讓head移動直到nullptr，同時跟著動dummy
  • 當head到nullptr時，dummy的下一個必為要刪除的元素，因此進行練表刪除動作
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* res = new ListNode(0,head);
        ListNode* dummy = res;
        for(int i=0;i<n;i++){
            head = head->next;
        }
        while(head != nullptr){
            head = head->next;
            dummy = dummy->next;
        }
        dummy->next = dummy->next->next;
        return res->next;
    }
};

Leetcode 138

  • 使用hashMap儲存已經便利過的元素，key為節點，value為節點的值，之所以用hashMap的原因是因為避免random指向尚未生成的節點
  • 之後在便利cur並且使用hashMap的key來當作Node
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
 
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(!head) return nullptr;
        Node* cur = head;
        unordered_map<Node*,Node*> old_to_new;
        old_to_new.clear();
        while(cur){
            old_to_new[cur] =new Node( cur->val);
            cur = cur->next;
        }
        cur = head;
        while(cur){
            old_to_new[cur]->next = old_to_new[cur->next];
            old_to_new[cur]->random = old_to_new[cur->random];
            cur = cur->next;
        }
        return old_to_new[head];
    }
};

Leetcode 2

  • merge 用dummy搭配tmp模板話,插入值用 new ListNode
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *dummy,*tmp;
        dummy = new ListNode();
        tmp = dummy;
        int carry = 0;
 
        while(l1 != nullptr || l2 != nullptr || carry != 0){     
            int v1 = (l1 != nullptr) ? l1->val : 0;
            int v2 = (l2 != nullptr) ? l2->val : 0;
            
            int v = v1 + v2 + carry;
            carry = v / 10;
            int sum = v%10;            
            tmp->next = new ListNode(sum);
            tmp = tmp -> next;
 
            if(l1 != nullptr)l1 = l1->next;
            if(l2 != nullptr)l2 = l2->next;
        }   
        return dummy->next;
    }
};