Open in app

Sign in

Write

Sign in

Python C++ lists

Jimmy (xiaoke) Shen
7 min readFeb 11, 2020

--

2. Add Two Numbers

The following code will get an error.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    int get_value(ListNode* list){
        int a = 0;
        ListNode* node = list;
        int i = 0;
        while(node!=NULL){
            a+= node->val*pow(10, i);
            i++;
            node = node->next;
        }
        return a;
    }
    ListNode* generate_list(int c){
        int last_dig = c%10;
        ListNode root = ListNode(last_dig);
        ListNode* res = &root;
       // ListNode* root = & node;
        //root->val=last_dig;
        cout<<last_dig<<endl;
        ListNode cur=root;
        //cout<<"cur"<<cur<<endl;
        cout<<"resres"<<res->val<<endl;
        while(10*c/10){
              int last_dig = c%10;
              c= c/10;
            cout<<last_dig<<endl;
              ListNode node=ListNode(last_dig);
              //cur->next = &node;
            cur.next = &node;
               //cout<<"node"<<(&node)<<endl;
              cur=node;
              }
        //cout<<"root"<<root<<endl;
        //cout<<"root.val"<<(root->val)<<endl;
        //cout<<"root.next"<<(root->next)<<endl;
        //cout<<"root.next"<<(root->next->val)<<endl;
        //int val = get_value(root);
        //cout<<"val"<<val<<endl;
        return res;
    }
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int a = get_value(l1), b= get_value(l2);
        int c = a+b;
        cout<<c<<endl;
        return generate_list(c);
        //cout<<"fina"<<(res->val)<<endl;
         //cout<<"fina"<<(res->next->val)<<endl;
        
        
        //return res;
        
    }
};

This one still has an error for the following test case:

It will have an overflow issue, however, the previous issue is not happened.

1560 / 1563 test cases passed./**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    unsigned long long get_value(ListNode* list){
        unsigned long long a = 0;
        ListNode* node = list;
        int i = 0;
        while(node!=NULL){
            a+=( unsigned long long)(node->val)*pow(10, i);
            i++;
            node = node->next;
        }
        return a;
    }
    ListNode* generate_list(unsigned long long c){
        int last_dig = int(c%10);
        ListNode* root =new ListNode(last_dig);
        ListNode* res = root;
        ListNode* cur=root;
        while(c/10){ 
             c= c/10;
            int last_dig = int(c%10);
            //cout<<last_dig<<endl;
              ListNode* node=new ListNode(last_dig);
            cur->next = node;
              cur=node;
              }
        return res;
    }
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
       unsigned long long a = get_value(l1), b= get_value(l2);
       unsigned long long c = a+b;
        cout<<c<<endl;
        return generate_list((unsigned long long)c);
        
    }
};

Python will not have above issue …

We can use this one to solve this problem safely.

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy_head = new ListNode(0);
        ListNode* cur = dummy_head;
        int carry = 0;
        while (l1 || l2 || carry) {
            int num = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + carry;
            carry = num / 10;
            cur->next = new ListNode(num % 10);
            cur = cur->next;
            if (l1) l1 = l1->next;
            if (l2) l2 = l2->next;
        }
        return dummy_head->next;
    }
};

python code

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 is None:return l2
        if l2 is None:return l1
        carry = 0
        head = ListNode(0)
        tail = head
        while l1 or l2 or carry:
            this_v = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry
            if l1:l1=l1.next
            if l2:l2=l2.next
            carry, this_v = divmod(this_v, 10)
            node = ListNode(this_v)
            tail.next = node
            tail = node
        return head.next

203. Remove Linked List Elements

https://leetcode.com/problems/remove-linked-list-elements/

recursion

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if(head==NULL)return NULL;
        if(head->val==val)return removeElements(head->next, val);
        else {
            head->next = removeElements(head->next, val);
            return head;
        }
    }
};

Or more concisely

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if(head==NULL)return NULL;
        head->next = removeElements(head->next,val);
        return head->val==val?head->next:head;
    }
};

Iterations

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        // handle the head value is val case.
        ListNode* dummy=new ListNode(-1);
        dummy->next = head;
        ListNode *pre=dummy, *cur=head;
        while(cur!=NULL){
            if(cur->val==val)pre->next = cur->next;//skip current when equal to val
            else pre=cur;
            cur = cur->next;
        }
        return dummy->next;
    }
};

Without using dummy

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        // handle the head value is val case.
        if(head==NULL)return NULL;
        while (head->val==val){
            head=head->next;
            if(head==NULL)return NULL;
        }
        //if(head==NULL)return NULL;
        ListNode *pre=head, *cur=head;
        while(cur!=NULL){
            if(cur->val==val){
                pre->next = cur->next;
                cur = cur->next;
            }
            else{
                pre = cur;
                cur = cur->next;
            }
        }
        return head;
    }
};

21. Merge Two Sorted Lists

Iteration

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* head = new ListNode(-1);
        ListNode* node=head;
        while(l1 || l2){
            if(l1 && l2){
                if (l1->val<l2->val){
                    node->next = l1;
                    node = l1;
                    l1 = l1->next;
                }
                else {
                    node->next = l2;
                    node = l2;
                    l2 = l2->next;
                }
            }
            else {
                if(l1) {node->next = l1;break;}
                if(l2) {node->next = l2; break;}
            }
            
        }
        return head->next;
        
    }
};

Or making the iteration more concise.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* dummy_head = new ListNode(INT_MIN);
        ListNode* tail=dummy_head;
        while(l1 && l2){
                if (l1->val<l2->val){
                    tail->next = l1;
                    tail = l1;
                    l1 = l1->next;
                }
                else {
                    tail->next = l2;
                    tail = l2;
                    l2 = l2->next;
                }
            }
        tail->next = l1?l1:l2;
        return dummy_head->next;
        
    }
};

Recursion

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1 && l2){
            if(l1->val<l2->val){
                auto nxt = mergeTwoLists(l1->next, l2);
                l1->next = nxt;
                return l1;
            }
            else{
               auto  nxt = mergeTwoLists(l1, l2->next);
                l2->next = nxt;
                return l2;
            }
        }
        else return l1?l1:l2;  
    }
};

Or even more concise

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
       if(l1 == NULL) return l2;
  if(l2 == NULL) return l1;
  if(l1->val < l2->val){
   l1->next = mergeTwoLists(l1->next, l2);
   return l1;
  } else{
   l2->next = mergeTwoLists(l1, l2->next);
   return l2;
  }
        
    }
};

993. Cousins in Binary Tree

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    unordered_map<int, pair<int, int>> m_;
public:
    void helper(TreeNode* node, int depth,int parent){
        if (node==NULL) return;
        m_[node->val]=make_pair(depth+1, parent);
        helper(node->left, depth+1, node->val);
        helper(node->right, depth+1, node->val);
    }
    bool isCousins(TreeNode* root, int x, int y) {
        helper(root, 0, INT_MAX);
        return x!=y && m_[x].first==m_[y].first &&  m_[x].second!=m_[y].second;
        
        
    }
};

430. Flatten a Multilevel Doubly Linked List

https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* prev;
    Node* next;
    Node* child;
};
class Node{
public:
int val;
Node* prev;
Node* next;
Node* child;
}*/
class Solution {
public:
    Node* flatten(Node* head) {
        for (Node* h = head; h; h = h->next){
            if (h->child){
                Node* next = h->next;
                h->next = h->child;
                h->next->prev = h;
                h->child = NULL;
                Node* p = h->next;
                while (p->next) p = p->next;
                p->next = next;
                if (next) next->prev = p;
            }
        }
 return head;
    }
};

Another slightly modified version with comments

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* prev;
    Node* next;
    Node* child;
};
class Node{
public:
int val;
Node* prev;
Node* next;
Node* child;
}*/
class Solution {
public:
    Node* flatten(Node* head) {
        Node* h=head;
        while (h!=NULL){
            if (h->child){
                //preserve old next
                Node* next = h->next;
                //update current node next to the first children node
                h->next = h->child;
                h->child->prev = h;
                h->child = NULL;
                //explore children node    
                Node* p=h->next;
                while(p->next)p=p->next;
                //connect old next with the last node of the children node
                p->next = next;
                if(next) next->prev=p;
            }
             h = h->next;
        }
 return head;
    }
};

https://www.geeksforgeeks.org/in-a-linked-list-given-only-a-pointer-to-a-node-to-be-deleted-in-a-singly-linked-list-how-do-you-delete-it/

Thanks.

445. Add Two Numbers II

python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1:return l2
        if not l2: return l1
        stack1, stack2 = [], []
        while l1:
            stack1.append(l1.val)
            l1 = l1.next
        while l2:
            stack2.append(l2.val)
            l2 = l2.next
        stack3, carry = [], 0
        while (stack1 or stack2 or carry):
            v1, v2 = stack1.pop() if stack1 else 0, stack2.pop() if stack2 else 0
            this_v = v1+v2+carry
            carry, this_v = divmod(this_v, 10)
            stack3.append(this_v)
        head = ListNode(stack3.pop())
        tail = head
        while stack3:
            node = ListNode(stack3.pop())
            tail.next = node
            tail = node
        return head

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        if(!l1)return l2;
        if(!l2)return l1;
        vector<int> stack1, stack2;
        while(l1){
            stack1.push_back(l1->val);
            l1 = l1->next;
        }
        while(l2){
            stack2.push_back(l2->val);
            l2 = l2->next;
        }
        vector<int> stack3;
        int carry = 0;
        while(!stack1.empty() || !stack2.empty() || carry){
            int this_val = (stack1.empty()?0:stack1.back())+(stack2.empty()?0:stack2.back())+carry;
            if(!stack1.empty())stack1.pop_back();
            if(!stack2.empty())stack2.pop_back();
            carry = this_val/10;
            stack3.push_back(this_val%10);
        }
        ListNode* head = new ListNode(stack3.back());
        stack3.pop_back();
        ListNode* tail = head;
        while(!stack3.empty()){
            ListNode* node = new ListNode(stack3.back());
            stack3.pop_back();
            tail->next = node;
            tail = node;
        }
          return head;  
        }
};

--

--

Jimmy (xiaoke) Shen
Jimmy (xiaoke) Shen

Written by Jimmy (xiaoke) Shen

306 Followers
351 Following

MLE/SWE @meta

No responses yet

Help

Status

About

Careers

Press

Blog

Privacy

Terms

Text to speech

Teams