L11. Add 1 to a number represented by LinkedList

Поділитися
Вставка
  • Опубліковано 16 гру 2024

КОМЕНТАРІ • 96

  • @AkshayNarsanne
    @AkshayNarsanne Рік тому +44

    Almost solved the entire series just 5 questions remaining thanks to you brother ❤❤❤❤

  • @ayushidalal5488
    @ayushidalal5488 Місяць тому +4

    The moment you said how we do this in basic maths - I paused the video and did a couple of dry runs and I was able to code both the approaches on my own, thankyou so much Striver! ❤

  • @adebisisheriff159
    @adebisisheriff159 10 місяців тому +11

    Thanks Striver!!!!!!!!!!! You are a rare gem!

  • @moksh7130
    @moksh7130 2 місяці тому +8

    Man oh man! One silly question, do you think of all these solutions by yourself? Sometimes looking at your explanations, i feel unreal because they so good

  • @yasaswinikarumuri9590
    @yasaswinikarumuri9590 4 місяці тому +6

    Such a great logic of using recursion! Ur a man with a great vision. Thank you striver

  • @hardikpatel352
    @hardikpatel352 7 місяців тому +4

    Explanation recursion by Striver is another level🔥🔥.

  • @muhammadawais-c2u
    @muhammadawais-c2u Рік тому +5

    Respected Sir, You and your work is great.

  • @VivekSharma-sk3vp
    @VivekSharma-sk3vp 5 місяців тому +2

    I have made the recursive code by myself ,thanks striver for providing amazing content..

  • @tedbundy8712
    @tedbundy8712 4 місяці тому +2

    Too good explanation sir
    you don't know how much you are helping me with this playlist

  • @chanduhl7060
    @chanduhl7060 Місяць тому

    The way you teaching recursive is different ❣️

  • @robot3.077
    @robot3.077 11 місяців тому +2

    😍😍😍😍😍God of dsa

  • @Manas-q8x
    @Manas-q8x 11 місяців тому +11

    An alternative solution without recursion or reversing the linked list. It includes traversing the linked list intially and maintaining a pointer with the last Non 9 element .
    After traversing the complete linked list we have three cases :
    CASE 1 : Last element is not 9 : Simply add the last data value and do nothing
    CASE 2 : Last element is 9 and there is a non9 element (its not null) : increase the last non 9 element by one (we have its reference) and traverse till the end making all data values as 0
    CASE 3 : Last element in 9 and there in non non9 element (it is null) : insert 1 at the start of the linkedlist and make all other element 0.
    Code for the same :
    class Solution
    {
    public static Node addOne(Node head)
    {
    Node h = head;
    Node lastNonNine = null;
    while(head.next!=null)
    {
    if(head.data !=9)
    {
    lastNonNine = head;
    }
    head = head.next;
    }
    if(head.data !=9)
    {
    head.data = head.data + 1;
    return h;
    }
    else {
    if(lastNonNine !=null)
    {
    lastNonNine.data = lastNonNine.data + 1;
    lastNonNine = lastNonNine.next;
    while(lastNonNine != head)
    {
    lastNonNine.data = 0;
    lastNonNine = lastNonNine.next;
    }
    head.data = 0;
    return h;
    }
    else
    {
    Node temp = new Node(1);
    temp.next = h;
    lastNonNine = h;
    while(lastNonNine != head)
    {
    lastNonNine.data = 0;
    lastNonNine = lastNonNine.next;
    }
    head.data = 0;
    return temp;
    }
    }
    }
    }

    • @anshusorrot316
      @anshusorrot316 8 місяців тому

      yes i have done by this way

    • @parthh1112
      @parthh1112 8 місяців тому

      very long code

    • @DrOnZeR2022
      @DrOnZeR2022 5 місяців тому

      It contains to much check condition which reduce the readability and understanding

    • @DEVANSHVYAS-z1b
      @DEVANSHVYAS-z1b 5 місяців тому +1

      @@DrOnZeR2022
      Node* addOne(Node *head)
      {
      Node *temp = head, *last = nullptr;
      while(temp) {
      if(temp->data != 9) last = temp;
      temp = temp->next;
      }
      if(last == nullptr) {
      Node *newHead = new Node(1);
      newHead->next = head;
      while(head) {
      head->data = 0;
      head = head->next;
      }
      return newHead;
      }
      else {
      last->data += 1;
      Node *makezero = last->next;
      while(makezero) {
      makezero->data = 0;
      makezero = makezero->next;
      }
      return head;
      }
      }

  • @PCCOERCoder
    @PCCOERCoder 19 днів тому +3

    Lecture successfully completed on 28/11/2024 🔥🔥k

  • @hareshnayak7302
    @hareshnayak7302 8 місяців тому +1

    Understood,thanks striver for this amazing video.

  • @learner7799
    @learner7799 11 місяців тому +9

    Really inspiring striver ❤..
    I just cant express how much we people love you.
    Thank you so much 🙌🥹

  • @Mel-up7un
    @Mel-up7un 2 місяці тому

    Understood both recursive and iterative approach!!😇Recursive one is a bit confusing but feels easier once you understand it

  • @Gaurav-qh1cy
    @Gaurav-qh1cy Рік тому +3

    int carry(Node* &temp){
    //base case
    if(!temp->next){
    int sum=temp->data+1;
    temp->data=sum%10;
    return sum/10;
    }
    int helper=carry(temp->next);
    if(!helper) return 0;
    int sum=temp->data+ helper;
    temp->data=sum%10;
    return sum/10;
    }
    Node *addOne(Node *head)
    { int x=carry(head);
    if(x) {
    Node* last_bit= new Node(x);
    last_bit->next=head;
    return last_bit;
    }
    return head;
    } //if anyone's looking for the recursive code ,i have written it ,nice video

  • @lucifersamrat6280
    @lucifersamrat6280 5 місяців тому

    great level of explanation sir!!!!

  • @HaamroNotes
    @HaamroNotes Місяць тому

    Implemented the helper function in my own way
    class Solution {
    public:
    int helper(Node *temp){
    if(temp==NULL)return 1;
    int sum=helper(temp->next)+temp->data;
    temp->data=sum%10;
    return sum/10;
    }
    Node* addOne(Node* head) {
    int carry=helper(head);
    if(carry==1){
    Node * newNode=new Node(1);
    newNode->next=head;
    return newNode;
    }
    return head;
    }
    };

  • @ayushtandon1719
    @ayushtandon1719 11 місяців тому +9

    there is a question on LC named ADD TWO NUMBERS II. Only difference is you need to add two numbers from end. Understood

  • @mahimagautam1810
    @mahimagautam1810 11 місяців тому +3

    In case of Error: replace addNode method to addOne

  • @arnabkundu1648
    @arnabkundu1648 6 місяців тому

    Understood. Thanks Striver.

  • @osuvoxbox7514
    @osuvoxbox7514 10 місяців тому +4

    Sorry sir but you didn't upload the solution sheet for this problem please upload it

  • @SibiRanganathL
    @SibiRanganathL 7 місяців тому

    Understood striver bhai

  • @Sarjais_Raja
    @Sarjais_Raja 3 місяці тому

    Just Amazing❤

  • @ReNaq313
    @ReNaq313 10 місяців тому

    Enjoying the playlist, please make playlist for trees, graphs please please

  • @akashverma5756
    @akashverma5756 11 місяців тому +4

    I think Recursive solution is overcomplicated for this problem.

  • @darshbothra007
    @darshbothra007 5 місяців тому

    amazing explaination

  • @shoaeebosman1886
    @shoaeebosman1886 Рік тому

    Coding Ninjas Java Compiler not working for this problem, but i have understood totally thank you

  • @yourhonestbro217
    @yourhonestbro217 6 місяців тому +1

    i had done the recursion one and the space complexity will be O(N) due to the recursion stack and this pisses me off ----''__''

  • @johndurai2226
    @johndurai2226 Рік тому

    super bro keep it up posting🎉🎉

  • @Adityasharma-xm2cn
    @Adityasharma-xm2cn 6 місяців тому +1

    we are using reverse(head) function and that uses a recursive approach then why that iterative solution doesn't uses a space complexity of O(2n) as we are using this recursive reverse(head) function 2 times?????

    • @Adityasharma-xm2cn
      @Adityasharma-xm2cn 6 місяців тому

      somebody know this then please reply....

    • @ashwinbalaji26
      @ashwinbalaji26 6 місяців тому

      We can reverse a LL in iterative way as well without taking any extra space. Watch his "reverse a Linked list" video, you will get it.

  • @ABISHEK-r7k
    @ABISHEK-r7k 10 місяців тому

    UNDERSTOOD SIR

  • @YourCodeVerse
    @YourCodeVerse 10 місяців тому

    Understood✅🔥🔥

  • @harshitpatil6138
    @harshitpatil6138 10 місяців тому

    Very Well Understood

  • @NazeerBashaShaik
    @NazeerBashaShaik 7 місяців тому

    Understood, thank you.

  • @harigs72
    @harigs72 2 місяці тому +1

    I have solved it Using two pointer
    Time complexity --O(2N) only if the all number in the list is 9 otherwise O(N)
    Space complexity -0(1);
    class Solution {
    public Node addOne(Node head) {
    // code here.
    Node nine=head.next;
    Node notnine=head;
    while(nine!=null){
    if(nine.data==9){
    nine=nine.next;
    }
    else{
    notnine=nine;
    nine=nine.next;
    }
    }
    int temp=head.data;
    while(notnine!=null){
    if(notnine.data==9){
    notnine.data=0;
    }
    else{
    notnine.data=notnine.data+1;
    }
    notnine=notnine.next;
    }
    Node newnode=new Node(1);
    Node temp2=head;
    if(head.data==0&&temp==9){
    head=newnode;
    newnode.next=temp2; }
    return head;
    }
    }

  • @Learnprogramming-q7f
    @Learnprogramming-q7f 9 місяців тому

    Thank you Bhaiya

  • @parthh1112
    @parthh1112 8 місяців тому

    class Solution
    {
    public:
    int findans(Node *&head){
    if(!head){
    return 1;
    }
    int c = findans(head -> next);
    int sum = c + head -> data;
    head -> data = sum % 10;
    return sum / 10;
    }
    Node* addOne(Node *head)
    {
    int car = findans(head);
    if(car){
    Node *n = new Node(1);
    n -> next = head;
    head = n;
    }
    return head;
    }
    };

  • @abhinavprabhat4418
    @abhinavprabhat4418 Рік тому +3

    Naive solution
    Node *reverse(Node* head){
    if(head == NULL || head->next ==NULL){
    return head;
    }
    Node *newhead = reverse(head->next);
    Node* front = head->next;
    front->next = head;
    head->next = NULL;
    return newhead;
    }
    Node *addOne(Node *head)
    {
    // naive solution

    head = reverse(head);
    Node* temp = head;
    int carry = 1;
    while(temp!=NULL){
    temp->data = temp->data+carry;
    if(temp->datadata =0;
    carry =1;
    }
    temp= temp->next;
    }
    if(carry ==1){
    Node* newNode= new Node(1);
    head = reverse(head);
    newNode->next = head;
    return newNode;
    }
    head = reverse(head);
    return head;

    }
    // better solution using recursion
    int helper(Node* temp, int &carry){
    if(temp == NULL){
    return 1;
    }
    carry = helper(temp->next,carry);
    temp->data = temp->data+carry;
    if(temp->data data=0;
    return 1;
    }
    }
    Node *addOne(Node *head)
    {

    /* better solution */
    int carry=0;
    carry = helper(head,carry);
    if(carry ==1){
    Node* newNode= new Node(1);

    newNode->next = head;
    return newNode;
    }
    return head;
    }

  • @souvikbiswas284
    @souvikbiswas284 22 дні тому

    can we not use stack instead of recursion??
    here's the code:
    class Solution:
    def addOne(self, head):
    if head is None:
    return ListNode(1)
    st = []
    curr = head
    while curr is not None:
    st.append(curr)
    curr = curr.next
    carry = 1
    while carry and st:
    node = st.pop()
    curr_val = node.val + carry
    node.val = curr_val % 10
    carry = curr_val // 10
    if carry == 0:
    break

    if carry:
    head = ListNode(1, head)

    return head
    In recursion the best case is also taking 2N time but here it can be O(1), we will break the loop as soon as the carry becomes 0.

  • @oyeshxrme
    @oyeshxrme 4 місяці тому

    thank you so much bhaiya

  • @DeadPoolx1712
    @DeadPoolx1712 3 місяці тому

    UNDERSTOOD;

  • @sahelidebnath5085
    @sahelidebnath5085 9 місяців тому

    class Solution
    {
    public static Node addOne(Node head)
    {
    Node temp = head;
    int[] carry = new int[1];
    carry[0] = 1;
    addOne(temp,carry);
    if(carry[0]>0){
    Node newNode = new Node(carry[0]);
    newNode.next = head;
    return newNode;
    }
    return head;
    }
    public static void addOne(Node root, int[] carry){
    if(root==null) return;
    addOne(root.next,carry);
    if(carry[0]==0) return;
    int sum = (root.data+carry[0]);
    root.data = sum%10;
    carry[0] = sum/10;
    }
    }

  • @ipsitadash6736
    @ipsitadash6736 11 місяців тому +1

    Why am I not able to think medium questions like this

    • @sakshisingh7159
      @sakshisingh7159 9 місяців тому

      Me too I just can't seem to think the solution .I mostly got blank no matter how much i try......

  • @missionmaths3867
    @missionmaths3867 8 місяців тому

    Understood 😃😃😃😃

  • @shashankverma2027
    @shashankverma2027 5 місяців тому +1

    Code is not present in links so here is java
    class Solution
    {
    public static Node rev(Node head) {
    Node temp = head;
    Node prev = null;
    while(temp != null){
    Node front = temp.next;
    temp.next = prev;
    prev = temp;
    temp = front;
    }
    return prev;
    }
    public static Node addOne(Node head)
    {
    if(head==null)return null;
    head=Solution.rev(head);
    Node tm=head;
    int carry=1;
    while(tm!=null){
    tm.data=tm.data+carry;
    if(tm.data0){
    Node n=new Node (carry);
    n.next=head;
    head=n;
    }

    return head;
    }
    }

  • @dhruvsovasaria
    @dhruvsovasaria Місяць тому

    thankyou

  • @shivisingh9975
    @shivisingh9975 6 місяців тому

    Understood!

  • @robot3.077
    @robot3.077 11 місяців тому +2

    An alternate solution for this Problem without recursion.
    Node* reverseLL(Node* head){
    if(head==NULL||head->next==NULL){
    return head;
    }
    Node* newhead=reverseLL(head->next);
    Node* front=head->next;
    front->next=head;
    head->next=NULL;
    return newhead;
    }
    Node *addOne(Node *head)
    {
    head=reverseLL(head);
    Node* temp=head;
    int carry=1;
    int sum=0;
    int newval;
    while(carry!=0&&temp!=NULL){
    sum=carry+temp->data;
    newval=sum%10;
    temp->data=newval;
    carry=sum/10;
    temp=temp->next;
    }
    if(carry){
    head=reverseLL(head);
    Node*newnode=new Node(carry,head);
    head=newnode;

    }
    else{
    head=reverseLL(head);

    }
    return head;

    }

  • @BoredToDeath2357
    @BoredToDeath2357 3 місяці тому

    Without reversing the LL and SC-O(1) & Tc-O(2n)
    class Solution {
    public:
    Node* addOne(Node* head) {
    Node* temp=head;
    Node* pos=nullptr;
    int val;
    while(temp->next){
    val=temp->next->data;
    if(val==9){
    if(!pos) pos=temp;
    }
    else pos=nullptr;
    temp=temp->next;
    }
    if(!pos) pos=temp;
    if(pos==head){
    if(head->data==9){
    Node* newH=new Node(1);
    newH->next=head;
    // head->data=0;
    head=newH;
    }
    }
    val=pos->data; ++val;
    pos->data=val%10;
    pos=pos->next;
    while(pos){
    pos->data=0;
    pos=pos->next;
    }
    return head;
    }
    };

  • @naveensah4000
    @naveensah4000 11 місяців тому

    Where are the notes

  • @RaviKumar-sn6tu
    @RaviKumar-sn6tu 6 місяців тому

    gem video

  • @codeman3828
    @codeman3828 10 місяців тому

    Undertsood

  • @guttulavybhav1030
    @guttulavybhav1030 5 місяців тому

    def helpp(self,temp):
    if(temp==None):
    return 1
    carry=self.helpp(temp.next)
    summ=temp.data+carry
    temp.data=summ%10
    if(summ>=10):
    return 1
    else:
    return 0
    def addOne(self,head):
    #Returns new head of linked List.
    carry=self.helpp(head)
    if(carry==1):
    p=Node(1)
    p.next=head
    return p
    return head
    can any one tell why my code is not passing some testcases in gfg

    • @PUNEETHKUMARVH
      @PUNEETHKUMARVH Місяць тому

      why doing mod 10? just check if it is equal to 10 and then proceed with logic.

  • @rajputadi01
    @rajputadi01 2 місяці тому

    I used a different logic
    Node* addOne(Node* head)
    {
    Node* tail = head;
    while(tail->next != NULL)
    {
    tail = tail->next;
    }
    if (tail->data < 9)
    {
    tail->data = tail->data + 1;
    return head;
    }
    Node* last_element_prev_to_9 = NULL;
    Node* temp = head;
    while(temp->next != NULL)
    {
    if ((temp->next->data == 9) && (temp->data != 9))
    {
    last_element_prev_to_9 = temp;
    }
    temp = temp->next;
    }
    if (last_element_prev_to_9 != NULL)
    {
    last_element_prev_to_9->data += 1;
    Node* temp = last_element_prev_to_9->next;
    while(temp != NULL)
    {
    temp->data = 0;
    temp = temp->next;
    }
    return head;
    }
    Node* dummy = new Node(1);
    Node* curr = head;
    while(curr != NULL)
    {
    curr->data = 0;
    curr = curr->next;
    }
    dummy->next = head;
    return dummy;
    }

  • @ganeshvhatkar9253
    @ganeshvhatkar9253 10 місяців тому

    Understood

  • @pradipkumarmukhi
    @pradipkumarmukhi 7 місяців тому

    Understood Man you damn it!!!!\

  • @harshitjaiswal9439
    @harshitjaiswal9439 10 місяців тому

    understood.

  • @kkrsna9130
    @kkrsna9130 Рік тому

    Striver Bhai apana Bhadrak ru na

    • @kkrsna9130
      @kkrsna9130 Рік тому +1

      I am also from Bhadrak

    • @rickseth9207
      @rickseth9207 10 місяців тому +1

      Where did you get the idea that he is from Bhadrak?

  • @utkarshsingh3319
    @utkarshsingh3319 Рік тому

    ❤❤

  • @anupkhismatrao9280
    @anupkhismatrao9280 9 місяців тому

  • @hardikpatel352
    @hardikpatel352 7 місяців тому +1

    undeerstood

  • @iamnoob7593
    @iamnoob7593 9 місяців тому

    US

  • @SamyakSharma-oy1bv
    @SamyakSharma-oy1bv Місяць тому

    respect ++;

  • @cenacr007
    @cenacr007 9 місяців тому

    us

  • @AkashKumarTiwary-u4b
    @AkashKumarTiwary-u4b 7 місяців тому

    god

  • @bhaskargowda-3955
    @bhaskargowda-3955 4 місяці тому

    Godly🙏🪄❤

  • @shashankshah2064
    @shashankshah2064 8 місяців тому

    public int addHelper(Node temp){
    if(temp == null){
    return 1;
    }
    int carry = addHelper(temp.next);
    temp.data = temp.data+carry;
    if(temp.data < 10) return 0;
    temp.data = 0;
    return 1;
    }
    public static Node addOne(Node head) {
    // Write your code here.
    Solution solution = new Solution();
    int carry = solution.addHelper(head);
    if(carry == 1){
    Node newNode = new Node(1);
    newNode.next = head;
    head = newNode;
    }
    return head;
    }

  • @hitmanop4078
    @hitmanop4078 3 місяці тому +1

    BRUTE FORCE ==>
    ```
    import java.math.BigInteger;
    import java.util.List;
    class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
    val = x;
    next = null;
    }
    }
    public class add1ToLL {
    public static ListNode addOne(ListNode head) {
    if (head == null) {
    return new ListNode(1);
    }
    // Reverse the linked list
    head = reverseLL(head);
    ListNode temp = head;
    int carry = 1;
    // Traverse the list and add one
    while (temp != null) {
    temp.val = temp.val + carry;
    if (temp.val < 10) {
    carry = 0;
    break;
    } else {
    temp.val = 0;
    carry = 1;
    }
    if (temp.next == null && carry == 1) {
    temp.next = new ListNode(0); // Add new node if needed
    }
    temp = temp.next;
    }
    // Reverse the linked list again to restore original order
    head = reverseLL(head);
    // If there is still a carry, add a new node at the front
    if (carry == 1) {
    ListNode newNode = new ListNode(1);
    newNode.next = head;
    return newNode;
    }
    return head;
    }
    private static ListNode reverseLL(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    ListNode next;
    while (curr != null) {
    next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
    }
    return prev;
    }
    // Helper method to create a linked list from an array.
    public static ListNode createLinkedList(int[] values) {
    if (values.length == 0)
    return null;
    ListNode head = new ListNode(values[0]);
    ListNode current = head;
    for (int i = 1; i < values.length; i++) {
    current.next = new ListNode(values[i]);
    current = current.next;
    }
    return head;
    }
    // Helper method to print the linked list.
    public static void printLinkedList(ListNode head) {
    ListNode current = head;
    while (current != null) {
    System.out.print(current.val);
    current = current.next;
    if (current != null) {
    System.out.print("->");
    }
    }
    System.out.println();
    }
    public static void main(String[] args) {
    // Test case 1: LinkedList 4->5->6
    int[] list1 = { 9 };
    ListNode head1 = createLinkedList(list1);
    System.out.print("Before: ");
    printLinkedList(head1);
    head1 = addOne(head1);
    System.out.print("After: ");
    printLinkedList(head1);
    // Test case 2: LinkedList 1->2->3
    int[] list2 = { 8, 4, 2, 1, 4, 1, 1, 7, 6, 7, 7, 6 };
    ListNode head2 = createLinkedList(list2);
    System.out.print("Before: ");
    printLinkedList(head2);
    head2 = addOne(head2);
    System.out.print("After: ");
    printLinkedList(head2);
    }
    }
    ```

  • @satyanarayanbarik1701
    @satyanarayanbarik1701 Місяць тому

    Unnderstood

  • @PritamSingh018
    @PritamSingh018 Місяць тому

    thank u bhaiya

  • @dewanandkumar8589
    @dewanandkumar8589 7 місяців тому

    Understood

  • @chiragbansod8252
    @chiragbansod8252 8 місяців тому

    understood

  • @VidhiSrivastava-lo9mj
    @VidhiSrivastava-lo9mj 6 місяців тому

    Understood

  • @abhinanda7049
    @abhinanda7049 8 місяців тому

    understood

  • @RajNamdev_19
    @RajNamdev_19 4 місяці тому +1

    Understood

  • @ashishpradhan6250
    @ashishpradhan6250 5 місяців тому

    understood

  • @rutujashelke4208
    @rutujashelke4208 3 місяці тому

    Understood

  • @sheeladevi1640
    @sheeladevi1640 3 місяці тому

    understood

  • @abhinavabhi3568
    @abhinavabhi3568 2 місяці тому

    Understood

  • @himasreedadam7670
    @himasreedadam7670 4 дні тому

    understood

  • @sanjayv-ef6ey
    @sanjayv-ef6ey 10 годин тому

    understood