Delete from End

Removing the last node in a singly linked list: if head == NULL, return NULL; if there is only one node, free(head) and return NULL; otherwise walk until cur->next is the tail (stop when cur->next->next == NULL), then free(cur->next) and set cur->next = NULL. The walk is O(n) in the list length. The head pointer only changes when the list becomes empty.

C program (return `head`)

The sample uses insert_begin (same as delete from beginning / insert at beginning) to build 10 20 30, then calls delete_end three times. Assign head = delete_end(head); only when you need the updated head (here the last call can make the list empty).

delete_end frees only the removed tail (or the only node)—not a full free_list.
After the last delete, head is NULL and the list is empty.

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

struct Node {
    int data;
    struct Node *next;
};

struct Node *insert_begin(struct Node *head, int data)
{
    struct Node *newNode = malloc(sizeof(struct Node));
    if (newNode == NULL)
        return head;

    newNode->data = data;
    newNode->next = head;
    return newNode;
}

struct Node *delete_end(struct Node *head)
{
    if (head == NULL)
        return NULL;

    if (head->next == NULL) {
        free(head);
        return NULL;
    }

    struct Node *cur = head;
    while (cur->next->next != NULL)
        cur = cur->next;

    free(cur->next);
    cur->next = NULL;
    return head;
}

void print_list(struct Node *head)
{
    struct Node *cur = head;
    while (cur != NULL) {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

int main(void)
{
    struct Node *head = NULL;

    head = insert_begin(head, 30);
    head = insert_begin(head, 20);
    head = insert_begin(head, 10);

    print_list(head);   /* 10 20 30 */

    head = delete_end(head);
    head = delete_end(head);
    head = delete_end(head);

    print_list(head);   /* empty list: newline only */

    return 0;
}

Program output

10 20 30

First print_list shows the list. After three delete_end calls, the second print_list prints only a newline (no numbers).

Overall program flow

Step	Operation	`head` points to	List state (values)
1	`head = NULL`	`NULL`	Empty list
2	`head = insert_begin(head, 30)`	Single node `30` at `0x1000`	`30`
3	`head = insert_begin(head, 20)`	New head `0x2000` → old head `0x1000`	`20 30`
4	`head = insert_begin(head, 10)`	New head `0x3000` → `0x2000` → `0x1000`	`10 20 30`
5	`print_list(head)`	`0x3000`	Output line: `10 20 30`
6	`head = delete_end(head)`	Still `0x3000`	`10 20` (tail `30` at `0x1000` freed)
7	`head = delete_end(head)`	Still `0x3000`	`10` (node `20` at `0x2000` freed)
8	`head = delete_end(head)`	`NULL`	Empty (only node `10` at `0x3000` freed)
9	`print_list(head)`	`NULL`	Output: newline only

Each `delete_end` call in detail

Call 1: delete_end — list 10 → 20 → 30 (head = 0x3000)

Step	Operation	Variable	Value
1	Not empty; more than one node	—	Enter walk branch
2	`cur` walks until before tail	`cur`	`0x3000` → `0x2000` (second-last)
3	`free(cur->next)`	—	Tail `0x1000` (`30`) freed
4	`cur->next = NULL`	`0x2000->next`	`NULL`
5	`return head`	return value	`0x3000` (unchanged)

After call 1:

head → [10 | 0x2000] → [20 | NULL]

Call 2: delete_end — list 10 → 20

Step	Operation	Variable	Value
1	`cur = head`; `cur->next->next` is `NULL`	`cur`	Stays `0x3000` (no loop body)
2	`free(cur->next)`	—	Node `0x2000` (`20`) freed
3	`cur->next = NULL`	`0x3000->next`	`NULL`
4	`return head`	—	`0x3000`

After call 2:

head → [10 | NULL]

Call 3: delete_end — single node 10 at 0x3000

Step	Operation	Variable	Value
1	`head->next == NULL`	—	One-node branch
2	`free(head)`	—	Block at `0x3000` released
3	`return NULL`	return value	`NULL`

After call 3:

head → NULL

Memory layout (example addresses)

List before any delete_end (after inserts)

Address	Node	`data`	`next`	Points to
`0x3000`	`n1` (head, inserted last)	10	`0x2000`	`n2`
`0x2000`	`n2` (inserted 2nd)	20	`0x1000`	`n3`
`0x1000`	`n3` (tail, inserted first)	30	`NULL`	nowhere

Visual representation

Before the first delete (after building with insert_begin):

head (0x3000)
   │
   ▼
┌──────────────┐    ┌──────────────┐    ┌──────────────┐
│ data: 10     │    │ data: 20     │    │ data: 30     │
│ next: 0x2000 ┼───→│ next: 0x1000 ┼───→│ next: NULL   │
└──────────────┘    └──────────────┘    └──────────────┘
     n1                   n2                   n3
 (inserted last)     (inserted 2nd)      (inserted first)

Detailed step-by-step: call 1 (remove tail `30`)

Inside delete_end when head is 0x3000 and the list is 10 → 20 → 30:

Line	Code	Before	After
1	`if (head == NULL)`	`head = 0x3000`	Skip `return NULL`
2	`if (head->next == NULL)`	`0x3000->next` is `0x2000`	Skip one-node branch
3	`cur = head;`	—	`cur = 0x3000`
4	`while (cur->next->next != NULL)`	First: `cur->next->next` is `0x1000`	`cur = 0x2000`; next iter: condition false
5	`free(cur->next);`	`cur` is `0x2000`, `cur->next` is `0x1000`	Tail node freed
6	`cur->next = NULL;`	—	`0x2000->next = NULL`
7	`return head;`	—	`head` still `0x3000` in `main`

Complexity summary

Operation	Time	Extra space
`delete_end` (no tail pointer)	`O(n)` — walk to second-last node; one-node list `O(1)`	`O(1)`
`insert_begin` (build demo list)	`O(1)` per call	`O(1)` per new node
`print_list`	`O(n)`	`O(1)`
Whole program (build + print + deletes + print)	Repeated tail delete `O(n²)` worst case over shrinking `n`; prints `O(n)`	`O(n)` nodes max before deletes

The key takeaway is that delete from the end of a singly linked list needs a scan from the head to find the predecessor of the tail—O(n) time per call without extra structure, unlike delete-from-head.

Alternative: keep a tail pointer (and often a doubly linked list) for O(1) access at both ends; or walk once and cache the second-last node if your API allows.