Lesson 4 Linked List

Application: Sparse Vector in Scientific Computing

polynomial: can be viewed as special case of sparse vector

Merging Sparse Vector

:c1 ->(3,6)->(5,4)->
:c2->(1,2)->(4,9)->(5,-4)->
Q: algorithm for “merging” sparse vectors
->(1,2)->(3,6)->(4,9)->
Solution(psuedo code):

while(!c1->end() && !c2->end()){
    if(c1->order<c2->order){
        res.insert_back(c1);c1++
    }
    else if(c1->order>c2->order){
        res.insert_back(c2);c2++
    }
    else{
        res.insert_back(c1"+"c2);c1++;c2++;
    }
}
insert_back others

“running cursors” algorithm:
similar for other uses, like dot product

• Real-World Usage of Sparse Vector: LIBSVM

double Kernel::dot(const svm_node *px, const svm_node *py){
    double sum = 0;
    while (px->index != -1 && py->index != -1){
        if(px->index == py->index){
            sum += px->value * py->value;
            ++px;
            ++py;
        }
        else{
            if(px->index > py->index)
                ++py;
            else
                ++px;
        }
    }
    return sum;
}

Linked List in Job interviews

shortcomings: discrete, not concentrated

Linked List Reversal

leetcode-cn/problems/reverse-linked-list

/**
 * 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* pre = NULL;
        ListNode* cur = head;
        while(cur!=NULL){
            ListNode* tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp; 
        }
    return pre;
    }
};

“Cycle” in Linked List?

tortoise-hare (turtle-rabbit algorithm)

leetcode-cn.com/problems/linked-list-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* fast = head, *slow = head;
        while(fast && fast->next){
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast)
            return true;
        }
        return false;
    }
};

pointer 1 : one step
pointer 2 : two step ——> two cursers

Middle of Linked List

leetcode-cn.com/problems/middle-of-the-linked-list

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};

two pass, or tortoise-hare algorithm