連結清單的一些算法

例題一：2.兩數相加

給你兩個非空的連結清單，表示兩個非負的整數。它們每位數字都是按照逆序的方式存儲的，并且每個節點隻能存儲一位數字。

輸入：l1 = [2,4,3], l2 = [5,6,4]

輸出：[7,0,8]

解釋：342 + 465 = 807.

注意：

1.判斷是否需要進位

2.如果最高位需要進位，( > 10 )增加一個新的節點存儲

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* L1,ListNode *L2){
        ListNode* H = new ListNode();
        ListNode* ptr = H;

        int carry = 0;
        while(L1||L2||carry){
            int val = carry;
            if(L1) val += L1->val,L1 = L1->next;
            if(L2) val += L2->val,L2 = L2->next;
            

            ListNode* node = new ListNode(val % 10);
            ptr->next = node;
            ptr = node;
            carry = val / 10;
        }
        return H->next;
    }
};
           

例題二：141.環形連結清單

如果連結清單中存在環，則傳回true，否則，傳回false

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *a = head;
        ListNode *b = head;

        if(!head){
            return false;
        }
        do{
            a = a->next;
            b = b->next;
            if(!b){
                break;
            }
            b = b->next;
        }while(a && b && a != b);

        return b != nullptr;
    }
};
           

例題三：142.環形連結清單II

給定一個連結清單，傳回連結清單開始入環的第一個節點。如果連結清單無環，則傳回null。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* a = head,*b = head;
        if(!head) return nullptr;
        int acout = 0,bcout = 0;
        do{
            a = a->next;
            acout++;
            b = b->next;
            bcout++;
            if(!b) break;
            b = b->next;
            bcout++;
        }while(a && b && a != b);
        if(!b) return nullptr;
        a = head;
        while(a!=b){
            a = a->next;
            b = b->next;
        }
        return a;
    }
};
           

例題四：160.相交連結清單

編寫一個程式，找到兩個單連結清單相交的起始節點。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* pa = headA,*pb = headB;
        
        while(pa != pb){
            if(!pa) pa = headB;
            else pa = pa->next;
            if(!pb) pb = headA;
            else pb = pb->next;
        }
        return pa;
    }
};