给你两个非空的链表,表示两个非负的整数。它们每位数字都是按照逆序的方式存储的,并且每个节点只能存储一位数字。
输入: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; } };
如果链表中存在环,则返回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; } };
给定一个链表,返回链表开始入环的第一个节点。如果链表无环,则返回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; } };
编写一个程序,找到两个单链表相交的起始节点。
/** * 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; } };