0
\$\begingroup\$

I have implemented a code to solve following problem. I would like to improve the code efficiency.

  • Pardon if I just printed out the result.
  • Code has O(N) time and constant space complexity.

Given a singly linked list and an integer k, remove the kth last element from the list.

  • k is guaranteed to be smaller than the length of the list.
  • The list is very long, so making more than one pass is prohibitively expensive.
  • Do this in constant space and in one pass.

I used a window with the length of k and 2 pointers to track kth last element in the list. 2 pointers are: (1): previous to the first element, (2): the last element of window:

llnode *prev = llist->head;
llnode *last = llist->head;

CODE:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct llnode
{
    int value;
    struct llnode *next;
} llnode;

typedef struct xllist
{
    llnode * head;
    llnode * tail;
    size_t length;
} xllist;

bool create_node(xllist *list, int value)
{
    llnode *node = malloc(sizeof *node);
    if(!node)
    {
        return false;
    }
    list->length++;

    node->value = value;
    node->next = NULL;
    if(!list->head)
    {
        list->head = node;
        list->tail = node;
    }
    list->tail->next = node;
    list->tail = node;
    return true;
}

bool del_element_from_last(xllist *llist, int k)
{
    printf("len:%d \n", llist->length);
    //window with 2 pointers, length of k
    //prev is the prev node to the window
    llnode *prev = llist->head;
    llnode *last = llist->head;

    if(k > (size_t)llist->length)
    {
        return false;
    }
    else if (k == (size_t)llist->length)
    {
        llist->head = llist->head->next;
        return true;
    }

    for(int i=0; i<k; i++)
    {
        last = last->next;
    }

    //move window until last reaches end
    while(last)
    {
        prev = prev->next;
        last = last->next;
    }

    //remove first node of the window
    printf("deleted element:%d \n", prev->next->value);
    prev->next = prev->next->next;

}

int main(void)
{
    /*Given a singly linked list and an integer k, remove the kth last element from the list.
    k is guaranteed to be smaller than the length of the list.
    The list is very long, so making more than one pass is prohibitively expensive.
    Do this in constant space and in one pass.*/
    xllist llist = {NULL, NULL, 0};

    for(int i=0; i<100; i++)
    {
        if(!create_node(&llist, 100+i))
            printf("create fail\n");
    }

    del_element_from_last(&llist, 15);

}
\$\endgroup\$
2
  • 2
    \$\begingroup\$ The wording of the task sounds to me like you are only given a linked list with an unknown length (and probably also an unknown tail). In that case, getting the length of the list would require an additional pass (which is not allowed). Therefore, you may be violating the rules of the task by using llist->length in the function del_element_from_last. If I am interpreting the wording of the task correctly, the function should have the following signature: bool del_element_from_last(llnode *head, int k). \$\endgroup\$ – Andreas Wenzel Dec 25 '20 at 11:14
  • \$\begingroup\$ @AndreasWenzel Please check revised version here: codereview.stackexchange.com/questions/254213/… \$\endgroup\$ – Erdenebat Ulziisaikhan Jan 2 at 8:53
1
\$\begingroup\$

Here is a pointless cast:

if(k > (size_t)llist->length)

llist->length is already of type size_t. Perhaps you meant (size_t)k > llist->length? But it would be much simpler (and more correct) to change the interface so that k is a size_t to begin with, I think.


A singly-linked list should not need a length member. Consider how you might solve this problem (still in constant space and linear time) without knowing the list length in advance.

Hint: you'll need two pointers, one following k elements behind the other.

\$\endgroup\$
11
  • \$\begingroup\$ They shall do it "in one pass", though, and you're suggesting two passes (with your two pointers). \$\endgroup\$ – Kelly Bundy Dec 26 '20 at 20:17
  • 1
    \$\begingroup\$ @Kelly, you're right, though the two simultaneous passes will have better performance than two distinct passes, due to better memory locality. \$\endgroup\$ – Toby Speight Dec 28 '20 at 14:47
  • 1
    \$\begingroup\$ @Erdenebat, if you didn't notice the casting problem, perhaps you've not enabled enough warnings from your compiler. E.g. gcc -Wall -Wextra -Werror \$\endgroup\$ – Toby Speight Dec 28 '20 at 14:48
  • 1
    \$\begingroup\$ @KellyBundy: I believe the rules of the task description are to be interpreted in such a way that traversing the array simultaneously with two pointers is to be considered a single pass. With your stricter interpretation, there is no solution, as far as I can tell. \$\endgroup\$ – Andreas Wenzel Jan 2 at 14:58
  • 1
    \$\begingroup\$ @AndreasWenzel Yeah, probably the problem setter doesn't know what they're talking about. LeetCode for example has this problem as well, and its official solution article calls the two parallel passes "one pass". Rather ridiculous. \$\endgroup\$ – Kelly Bundy Jan 2 at 18:28
3
\$\begingroup\$

I don't know what OS and compiler you use but running gcc -O2 main.c -o main -Wall -Wextra produces several warnings:

main.c: In function ‘del_element_from_last’:
main.c:41:18: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘size_t’ {aka ‘long unsigned int’} [-Wformat=]
   41 |     printf("len:%d \n", llist->length);
      |                 ~^      ~~~~~~~~~~~~~
      |                  |           |
      |                  int         size_t {aka long unsigned int}
      |                 %ld
main.c:47:10: warning: comparison of integer expressions of different signedness: ‘int’ and ‘long unsigned int’ [-Wsign-compare]
   47 |     if(k > (size_t)llist->length)
      |          ^
main.c:51:16: warning: comparison of integer expressions of different signedness: ‘int’ and ‘long unsigned int’ [-Wsign-compare]
   51 |     else if (k == (size_t)llist->length)
      |                ^~
main.c:73:1: warning: control reaches end of non-void function [-Wreturn-type]
   73 | }
      | ^

valgrind reports memory leak:

$ valgrind ./main
==10611== Memcheck, a memory error detector
==10611== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==10611== Using Valgrind-3.16.1 and LibVEX; rerun with -h for copyright info
==10611== Command: ./main
==10611==
len:100
deleted element:186
==10611==
==10611== HEAP SUMMARY:
==10611==     in use at exit: 1,600 bytes in 100 blocks
==10611==   total heap usage: 101 allocs, 1 frees, 2,624 bytes allocated
==10611==
==10611== LEAK SUMMARY:
==10611==    definitely lost: 32 bytes in 2 blocks
==10611==    indirectly lost: 1,568 bytes in 98 blocks
==10611==      possibly lost: 0 bytes in 0 blocks
==10611==    still reachable: 0 bytes in 0 blocks
==10611==         suppressed: 0 bytes in 0 blocks
==10611== Rerun with --leak-check=full to see details of leaked memory
==10611==
==10611== For lists of detected and suppressed errors, rerun with: -s
==10611== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)`

Why does this function

bool del_element_from_last(xllist *llist, int k)

and others return non-zero on success? Usually, functions in C return 0 on success and non-zero on failure. The current behavior in your code is counter-intuitive.

You should add a function that prints the entire list.

If you do this:

del_element_from_last(&llist, 1);

your code crashes:

$ ./main
len:100
Segmentation fault
\$\endgroup\$
2
  • \$\begingroup\$ "Usually, functions in C return 0 on success and non-zero on failure." -- That applies to functions with a return type of int. However, with the return type of bool, in my opinion, it does make sense to make true indicate success. For example, many Windows API functions do this. But I agree that it can be confusing if the meaning is inverted depending on the return type, so maybe you are right that it should not be done. \$\endgroup\$ – Andreas Wenzel Dec 25 '20 at 10:59
  • \$\begingroup\$ Revised version here: codereview.stackexchange.com/questions/254213/… \$\endgroup\$ – Erdenebat Ulziisaikhan Jan 2 at 8:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.