How to add 1 number to a number represented linked list

[Question]: Number is represented in linked list such that each digit corresponds to a node in linked list. Add 1 to it. For example 1999 is represented as (1-> 9-> 9 -> 9) and adding 1 to it should change it to (2->0->0->0) 

#Approach:

  1. Reverse linked list. For example, 1-> 9-> 9 -> 9 is reversed to 9-> 9 -> 9 ->1.
  2. Start traversing linked list from leftmost node and add 1 to it. If there is a carry, move to the next node. Keep moving to the next node while there is a carry.
  3. Reverse modified linked list and return head.
func addOneUtil(_ head: ListNode?) -> ListNode? {
    let res = head // res is head node of the resultant list
    var temp: ListNode?
    var headCopy = head
    var carry = 1, sum = 0
    
    while headCopy != nil {
        // Calculate value of next digit in resultant list. The next digit is sum of following things (i) Carry (ii) Next digit of head list (if there is a next digit)
        sum = carry + headCopy!.val
        
        // update carry for next calculation
        carry = (sum >= 10) ? 1 : 0
        
        // update sum if it's greater than 10
        sum = sum % 10
        
        // Create a new node with sum as data
        headCopy?.val = sum
        
        // Move head and second pointers to next nodes
        temp = headCopy
        headCopy = headCopy?.next
    }
    
    // if some carry is still there, add a new node to result list. example 999+1 = 1000 where 0 is new node.
    if carry > 0 {
        temp?.next = ListNode(carry)
    }
    return res// return head of the resultant list
}

// This function mainly uses addOneUtil().
func addOne(_ head: ListNode?) -> ListNode? {
    var headCopy = head
    // Reverse linked list
    headCopy = reverseList2(headCopy)
    // Add one from left to right of reversed list
    headCopy = addOneUtil(headCopy)
    // Reverse the modified list
    return reverseList2(headCopy)
}

var linkListForAddOne =  ListNode(9, ListNode(9, ListNode(9)))
let addedOneList = addOne(linkListForAddOne)
//print("addedOne to the linkedList  --", addedOneList!)// 1->0->0->0

Leave a Comment

Your email address will not be published. Required fields are marked *