COMP104LinkedListAlgorithms/Slide1Some SimpleAlgorithms on Linked ListsWrite a function that returns the lengthofagivenlist.Write a booleanfunctionthat testswhether a given unsorted list ofcharacters isa palindromeWrite afunctionthat computesthe unionoftwo sorted linked lists of integers
COMP104 Linked List Algorithms / Slide 1 Some Simple Algorithms on Linked Lists Write a function that returns the length of a given list. Write a boolean function that tests whether a given unsorted list of characters is a palindrome. Write a function that computes the union of two sorted linked lists of integers
您The lengthof agiven list:int length (NodePtr Head)int size = O;NodePtr cur = Head;while(cur!=NULL)(size++;cur = cur->next;return size;
int length(NodePtr Head) { int size = 0; NodePtr cur = Head; while(cur != NULL){ size++; cur = cur->next; } return size; } The length of a given list:
Itcanalsoberecursive:int lengthRec (NodePtr Head)if(Head==NULL)return o;returnlength(Head->next)+ 1;
int lengthRec(NodePtr Head) { if(Head==NULL) return 0; return length(Head->next) + 1; } It can also be recursive:
COMP104LinkedListAlgorithms/Slide4Test ifthegiven listisapalindrome:[abcddcba]isapalindrome,[abcdc]is not.bool isPalindrome(NodePtr head)(. create a newlist in inverse order,newList2. check the twolists,head and newList, whetherthey are the same
COMP104 Linked List Algorithms / Slide 4 bool isPalindrome(NodePtr head) { 1. create a new list in inverse order, newList 2. check the two lists, head and newList, whether they are the same } Test if the given list is a palindrome: [a b c d d c b a] is a palindrome, [a b c d c] is not
Testifthegivenlistisapalindrome:bool isPalindrome(NodePtr Head)bool result;// copy the list in reverse orderNodePtr newList= NULL;NodePtr cur = Head;while(cur != NULL)(addHead(newList, cur->data);cur = cur->next;// compare the list and reversed listresult =true;//assumetruecur = Head;rev = newList;while(cur!=NULL)(if(cur->data != rev->data）result = false;//inot palindrome!cur = cur->next;rev = rev->next;while(newList!=NULL)(//delete reversed listcur = newList,newList = newList->next;delete cur;// all same; must bepalindrome!return result;
bool isPalindrome(NodePtr Head){ bool result; // copy the list in reverse order NodePtr newList = NULL; NodePtr cur = Head; while(cur != NULL){ addHead(newList, cur->data); cur = cur->next; } // compare the list and reversed list result = true; // assume true cur = Head; rev = newList; while(cur!=NULL){ if(cur->data != rev->data) result = false; // not palindrome! cur = cur->next; rev = rev->next; } while(newList != NULL){ // delete reversed list cur = newList; newList = newList->next; delete cur; } return result; // all same; must be palindrome! } Test if the given list is a palindrome: