Delete all occurrences of a given key in a linked list ?

• Given a singly linked list, delete all occurrences of a given key in it. For example,

[pastacode lang=”markdown” manual=”Input%3A%20%202%20-%3E%201%20-%3E%208%20-%3E%202%20-%3E%20%203%20-%3E%20%202%20-%3E%207%0A%20%20%20%20%20%20%20Key%20to%20delete%20%3D%202%0AOutput%3A%20%201%20-%3E%208%20-%3E%203%20-%3E%207%20″ message=”” highlight=”” provider=”manual”/]

Sample Code in C

[pastacode lang=”c” manual=”%23include%20%3Cstdio.h%3E%20%0A%23include%20%3Cstdlib.h%3E%20%0A%2F%2F%20A%20linked%20list%20node%20%0Astruct%20Node%20%0A%7B%20%0A%20%20%20%20int%20data%3B%20%0A%20%20%20%20struct%20Node%20*next%3B%20%0A%7D%3B%20%0A%2F*%20Given%20a%20reference%20(pointer%20to%20pointer)%20to%20the%20head%20of%20a%20list%20%0A%20%20%20and%20an%20int%2C%20inserts%20a%20new%20node%20on%20the%20front%20of%20the%20list.%20*%2F%0Avoid%20push(struct%20Node**%20head_ref%2C%20int%20new_data)%20%0A%7B%20%0A%20%20%20%20struct%20Node*%20new_node%20%3D%20(struct%20Node*)%20malloc(sizeof(struct%20Node))%3B%20%0A%20%20%20%20new_node-%3Edata%20%20%3D%20new_data%3B%20%0A%20%20%20%20new_node-%3Enext%20%3D%20(*head_ref)%3B%20%0A%20%20%20%20(*head_ref)%20%20%20%20%3D%20new_node%3B%20%0A%7D%20%0A%2F*%20Given%20a%20reference%20(pointer%20to%20pointer)%20to%20the%20head%20of%20a%20list%20and%20%0A%20%20%20a%20key%2C%20deletes%20all%20occurrence%20of%20the%20given%20key%20in%20linked%20list%20*%2F%0Avoid%20deleteKey(struct%20Node%20**head_ref%2C%20int%20key)%20%0A%7B%20%0A%20%20%20%20%2F%2F%20Store%20head%20node%20%0A%20%20%20%20struct%20Node*%20temp%20%3D%20*head_ref%2C%20*prev%3B%20%0A%20%20%20%20%2F%2F%20If%20head%20node%20itself%20holds%20the%20key%20or%20multiple%20occurrences%20of%20key%20%0A%20%20%20%20while%20(temp%20!%3D%20NULL%20%26%26%20temp-%3Edata%20%3D%3D%20key)%20%0A%20%20%20%20%7B%20%0A%20%20%20%20%20%20%20%20*head_ref%20%3D%20temp-%3Enext%3B%20%20%20%2F%2F%20Changed%20head%20%0A%20%20%20%20%20%20%20%20free(temp)%3B%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20free%20old%20head%20%0A%20%20%20%20%20%20%20%20temp%20%3D%20*head_ref%3B%20%20%20%20%20%20%20%20%20%2F%2F%20Change%20Temp%20%0A%20%20%20%20%7D%20%0A%20%20%20%20%2F%2F%20Delete%20occurrences%20other%20than%20head%20%0A%20%20%20%20while%20(temp%20!%3D%20NULL)%20%0A%20%20%20%20%7B%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Search%20for%20the%20key%20to%20be%20deleted%2C%20keep%20track%20of%20the%20%0A%20%20%20%20%20%20%20%20%2F%2F%20previous%20node%20as%20we%20need%20to%20change%20’prev-%3Enext’%20%0A%20%20%20%20%20%20%20%20while%20(temp%20!%3D%20NULL%20%26%26%20temp-%3Edata%20!%3D%20key)%20%0A%20%20%20%20%20%20%20%20%7B%20%0A%20%20%20%20%20%20%20%20%20%20%20%20prev%20%3D%20temp%3B%20%0A%20%20%20%20%20%20%20%20%20%20%20%20temp%20%3D%20temp-%3Enext%3B%20%0A%20%20%20%20%20%20%20%20%7D%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20key%20was%20not%20present%20in%20linked%20list%20%0A%20%20%20%20%20%20%20%20if%20(temp%20%3D%3D%20NULL)%20return%3B%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Unlink%20the%20node%20from%20linked%20list%20%0A%20%20%20%20%20%20%20%20prev-%3Enext%20%3D%20temp-%3Enext%3B%20%0A%20%20%20%20%20%20%20%20free(temp)%3B%20%20%2F%2F%20Free%20memory%20%0A%20%20%20%20%20%20%20%20%2F%2FUpdate%20Temp%20for%20next%20iteration%20of%20outer%20loop%20%0A%20%20%20%20%20%20%20%20temp%20%3D%20prev-%3Enext%3B%20%0A%20%20%20%20%7D%20%0A%7D%20%0A%2F%2F%20This%20function%20prints%20contents%20of%20linked%20list%20starting%20from%20%0A%2F%2F%20the%20given%20node%20%0Avoid%20printList(struct%20Node%20*node)%20%0A%7B%20%0A%20%20%20%20while%20(node%20!%3D%20NULL)%20%0A%20%20%20%20%7B%20%0A%20%20%20%20%20%20%20%20printf(%22%20%25d%20%22%2C%20node-%3Edata)%3B%20%0A%20%20%20%20%20%20%20%20node%20%3D%20node-%3Enext%3B%20%0A%20%20%20%20%7D%20%0A%7D%20%0A%20%20%20%2F*%20Drier%20program%20to%20test%20above%20functions*%2F%0Aint%20main()%20%0A%7B%20%0A%20%20%20%20%2F*%20Start%20with%20the%20empty%20list%20*%2F%0A%20%20%20%20struct%20Node*%20head%20%3D%20NULL%3B%20%0A%20%20%20%20push(%26head%2C%207)%3B%20%0A%20%20%20%20push(%26head%2C%202)%3B%20%0A%20%20%20%20push(%26head%2C%203)%3B%20%0A%20%20%20%20push(%26head%2C%202)%3B%20%0A%20%20%20%20push(%26head%2C%208)%3B%20%0A%20%20%20%20push(%26head%2C%201)%3B%20%0A%20%20%20%20push(%26head%2C%202)%3B%20%0A%20%20%20%20push(%26head%2C%202)%3B%20%0A%20%20%20%20int%20key%20%3D%202%3B%20%2F%2F%20key%20to%20delete%20%0A%20%20%20%20puts(%22Created%20Linked%20List%3A%20%22)%3B%20%0A%20%20%20%20printList(head)%3B%20%0A%20%20%20%20deleteKey(%26head%2C%20key)%3B%20%0A%20%20%20%20puts(%22%5CnLinked%20List%20after%20Deletion%3A%20%22)%3B%20%0A%20%20%20%20printList(head)%3B%20%0A%20%20%20%20return%200%3B%20%0A%7D” message=”” highlight=”” provider=”manual”/]