删除非空单链表最后一个值为x的结点

好的，针对你的问题，我可以给出以下的解法：

1. 遍历链表，找到最后一个值为x的结点。

2. 如果找到了这样的结点，记录它的前一个结点pre和后一个结点next。

3. 将pre结点的next指针指向next结点，删除中间的结点。

4. 如果没有找到这样的结点，直接返回原链表。

下面是C++的实现代码：

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode* removeLastValue(ListNode* head, int x) {
    ListNode *pre = NULL, *cur = head, *next = NULL;
    while (cur) {
        if (cur->val == x) {
            pre = cur;
            next = cur->next;
        }
        cur = cur->next;
    }
    if (pre && next) {
        pre->next = next->next;
        delete next;
    }
    return head;
}

注意：如果链表中有多个值为x的结点，此方法只删除最后一个。

相关问题

在带头结点的非空单链表L中查找值为x的结点

1. 初始化指针p为L的头结点的下一个结点。
2. 当p不为空时，执行以下操作：
a. 如果p的值等于x，返回p。
b. 否则，将p指向下一个结点。
3. 如果循环结束仍未找到值为x的结点，则返回空指针。

一个算法，在带头结点的非空单链表L中查找值为x的结点，若找到了这样的结点，输出“存在该元素”标志；否则输出“不存在该元素”标志。

### 回答1：
1. 初始化指针p指向单链表的头结点。
2. 当p不为NULL时，比较p所指向的结点数据域与x的值。
a. 若相等，则输出“存在该元素”标志，结束查找。
b. 若不相等，则将p指向下一个结点。
3. 若p为NULL，则输出“不存在该元素”标志，结束查找。

算法实现：

void searchNode(LinkList L, int x) {
    ListNode *p = L->next;
    while (p != NULL) {
        if (p->data == x) {
            printf("存在该元素\n");
            return;
        }
        p = p->next;
    }
    printf("不存在该元素\n");
}

### 回答2：
要在带头结点的非空单链表L中查找值为x的结点，可以使用以下算法实现。

1. 将链表L的头指针赋值给一个临时指针变量p，即p指向链表的第一个结点。

2. 对p进行循环，直到p指向空，每次循环都执行下面的操作。

1) 如果p结点的数据域的值等于x，说明找到了值为x的结点，输出“存在该元素”标志，结束算法。

2) 否则，将p的下一个结点的地址赋值给p，即p指向下一个结点。

3. 如果循环结束时仍然没有找到值为x的结点，说明不存在该元素，输出“不存在该元素”标志。

该算法的时间复杂度为O(n)，其中n为链表L的长度。下面是算法的Python代码实现：

def find_node(L, x):
    p = L.next  # 头结点的下一个结点
    while p != None:
        if p.data == x:
            print("存在该元素")
            return
        p = p.next
    print("不存在该元素")

使用该算法可以在带头结点的非空单链表L中查找值为x的结点，成功找到该结点时输出“存在该元素”标志，否则输出“不存在该元素”标志。

### 回答3：
以下是一种算法实现，在带头结点的非空单链表L中查找值为x的结点：

1. 初始化一个指针p，指向L的头节点的下一个节点（即第一个实际节点）。
2. 循环遍历链表，直到p指向链表的尾节点或者找到值为x的结点：
- 如果当前节点p的值等于x，则输出“存在该元素”标志，并结束循环。
- 否则，将p指向下一个节点，继续循环。
3. 如果循环结束后p指向链表的尾节点，说明没有找到值为x的结点，则输出“不存在该元素”标志。

具体实现代码如下：

def search_node(L, x):
    p = L.next  # 初始化指针p
    while p is not None and p.value != x:
        p = p.next  # 移动指针p
    if p is not None:  # 找到值为x的节点
        print("存在该元素")
    else:
        print("不存在该元素")

# 测试
L = LinkedList()  # 初始化带头结点的非空单链表L
# 往L中添加节点...
search_node(L, x)

该算法的时间复杂度为O(n)，其中n为链表长度。由于需要遍历整个链表来查找目标节点，所以算法的时间复杂度与链表长度成正比。