leetcode刷题笔记：链表

leetcode刷题笔记：链表

 

2.两数相加

 

 

class Solution {
public:
    ListNode* addTwonumbers(ListNode* l1, ListNode* l2)
    {
        ListNode*p1=l1,*p2=l2;
        //建立dummy首节点
        ListNode*dummy=new ListNode(-1);
        //p建立新的链表
        ListNode*p=dummy;
        int carry=0;//记录进位
        while(p1!=nullptr||p2!=nullptr||carry>0)
        {
            int val=carry;
            if(p1!=nullptr)
            {
                val+=p1->val;
                p1=p1->next;
            }
            if(p2!=nullptr)
            {
                val+=p2->val;
                p2=p2->next;
            }
            carry=val/10;
            val=val%10;
            p=p->next=new ListNode(val);
            
        }
        return dummy->next;
    }
};

21.合并两个有序链表

 

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) 
    {
        ListNode*dummy=new ListNode(-1);
        ListNode*p=dummy;
        ListNode*p1=list1,*p2=list2;
        while(p1!=nullptr&&p2!=nullptr)
        {
            if(p1->val>p2->val)
            {
                p->next=p2;
                p2=p2->next;
            }
            else
            {
                p->next=p1;
                p1=p1->next;
            }
            p=p->next;
        }
        if(p1!=nullptr) p->next=p1;
        if(p2!=nullptr) p->next=p2;
        return dummy->next;
    }
};

206.反转链表（递归）

 

 

class Solution {
public:
    ListNode* reverseList(ListNode* head) 
    {
        
         if(head==nullptr||head->next==nullptr) return head;
          ListNode *last=reverseList(head->next);
          head->next->next=head;
          head->next=nullptr;
          return last;
    }
};