7-5 链表倒数n个结点的乘积

链表倒数第n个节点的乘积是指在一个单向链表中，从最后一个节点开始向前数到第n个节点（包括第n个节点），将这些节点的值相乘得到的结果。这个操作通常需要先遍历链表找到第n个节点，然后回溯计算中间所有节点的值。

解决这个问题的一个常见算法是使用两个指针。第一个指针（p1）每次向前移动一步，第二个指针（p2）初始设为NULL，并且每次移动两步直到遇到p1。这样，当p2到达n的位置时，p1就指向了倒数第n个节点。之后，我们可以记录下每个节点的值并更新总乘积。

Python伪代码示例：

def product_of_last_n_nodes(head, n):
    if head is None or n <= 0:
        return None

    # 使用快慢指针法
    p1 = p2 = head
    product = 1
    for _ in range(n - 1):
        p2 = p2.next

    while p2:
        temp = p2.val
        p2 = p2.next
        product *= temp

    # 回溯更新product
    while p1 != p2:
        product *= p1.val
        p1 = p1.next

    return product

相关问题

链表倒数n个结点的乘积c++

题目描述：

输入一个链表，输出该链表倒数第n个结点的值的乘积c。假设链表中结点的值互不相同，且n一定小于链表的长度。

思路：

我们可以先遍历一遍链表，得到链表的长度len，然后再遍历一遍链表，找到倒数第n个结点，计算乘积c。

代码实现：

class ListNode:
def __init__(self, x):
self.val = x
self.next = None

def find_last_n_node_multiply(head, n):
if not head or n <= 0:
return None
len = 0
p = head
while p:
len += 1
p = p.next
if n > len:
return None
p = head
for i in range(len - n):
p = p.next
c = 1
while p:
c *= p.val
p = p.next
return c

# 测试代码
if __name__ == '__main__':
# 创建链表 1 -> 2 -> 3 -> 4 -> 5 -> 6
head = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node5 = ListNode(5)
node6 = ListNode(6)
head.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
node5.next = node6

print(find_last_n_node_multiply(head, 3)) # 120

求链式线性表倒数n个结点乘积 c语言

链式线性表的倒数第 n 个节点乘积通常涉及到遍历链表并维护中间节点的值。由于链表的特性，直接访问某个特定索引的元素并不直观，因此需要先找到链表的长度，然后从尾部开始向前移动相应步数。

以下是用 C 语言实现的一个基本思路：

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

// 链表节点结构体
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 计算链表长度
int getLength(Node* head) {
    int length = 0;
    while (head != NULL) {
        length++;
        head = head->next;
    }
    return length;
}

// 创建新的节点
Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

// 递归计算倒数第 n 个节点的前一个节点的乘积
int productOfLastNth(Node* head, int n) {
    if (n == 1 || head == NULL) { // 如果 n=1 或链表为空，则返回当前节点的值
        return head->data;
    } else if (n > 1) {
        Node* current = head; // 开始从头节点开始
        for (int i = 1; i < n - 1; i++) { // 跳过前 n-1 个节点
            current = current->next;
        }
        int product = productOfLastNth(current->next, n - 1); // 递归求剩余部分的乘积
        return product * current->data; // 返回当前节点的数据与剩余部分乘积的乘积
    }
}

int main() {
    // 创建示例链表
    Node* listHead = createNode(1);
    listHead->next = createNode(2);
    listHead->next->next = createNode(3);
    listHead->next->next->next = createNode(4);

    int n = 2; // 求倒数第二个节点的乘积
    int result = productOfLastNth(listHead, n);
    printf("倒数第 %d 个节点的前一个节点乘积为: %d\n", n, result);

    return 0;
}

这个程序首先定义了一个链表结构，并实现了计算链表长度以及递归计算倒数第 n 个节点前一个节点乘积的功能。在 `main` 函数中创建了链表并调用了该函数。