链表及其算法

本文主要是介绍链表及其算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

例题一：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;
    }
};

这篇关于链表及其算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！