Compare numbers represented by Linked Lists | C ++ implementation of the approach ; Structure for a linked list node ; A helper function to remove zeros from the start of the linked list ; A helper function to find the length of linked list ; Given a reference ( pointer to pointer ) to the head of a list and an int , push a new node on the front of the list . ; Allocate node ; Set the data ; Link the old list after the new node ; Set the head to point to the new node ; Function to compare the numbers represented as linked lists ; Remover leading zeroes from the linked lists ; Since the number represented by a has a greater length , it will be greater ; If the lengths of two numbers are equal we have to check their magnitudes ; If we reach here , then a and b are not NULL and their data is same , so move to next nodes in both lists ; If linked lists are identical , then we need to return zero ; Driver code ; The constructed linked lists are : a : 5 -> 6 -> 7 b : 2 -> 3 -> 3
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; struct Node * next ; } ; Node * removeLeadingZeros ( struct Node * a ) { if ( a != NULL && a -> data == 0 ) return removeLeadingZeros ( a -> next ) ; else return a ; } int getSize ( struct Node * a ) { int sz = 0 ; while ( a != NULL ) { a = a -> next ; sz ++ ; } return sz ; } void push ( struct Node * * head_ref , int new_data ) { struct Node * new_node = ( struct Node * ) malloc ( sizeof ( struct Node ) ) ; new_node -> data = new_data ; new_node -> next = ( * head_ref ) ; ( * head_ref ) = new_node ; } int compare ( struct Node * a , struct Node * b ) { a = removeLeadingZeros ( a ) ; b = removeLeadingZeros ( b ) ; int lenA = getSize ( a ) ; int lenB = getSize ( b ) ; if ( lenA > lenB ) { return 1 ; } else if ( lenB > lenA ) { return -1 ; } while ( a != NULL && b != NULL ) { if ( a -> data > b -> data ) return 1 ; else if ( a -> data < b -> data ) return -1 ; a = a -> next ; b = b -> next ; } return 0 ; } int main ( ) { struct Node * a = NULL ; push ( & a , 7 ) ; push ( & a , 6 ) ; push ( & a , 5 ) ; struct Node * b = NULL ; push ( & b , 3 ) ; push ( & b , 3 ) ; push ( & b , 2 ) ; cout << compare ( a , b ) ; return 0 ; }