如何删除链表的中间节点和a/b处的节点？

文章目录

- - 删除中间节点
  - 删除 a/b 处的节点
- 示例
- - - 定义链表节点结构
    - 删除中间节点
    - 删除 a/b 处的节点
  - 注意事项
- Python 实现案例
- - 创建链表
  - 删除中间节点
  - 删除 a/b 处的节点
  - 测试代码
  - 示例代码完整版
  - 测试输出

在链表中删除中间节点或者特定位置（如 a/b 处）的节点涉及到一些基本的链表操作。下面我将分别解释这两种情况下的处理方法。

删除中间节点

假设“中间节点”是指链表从头到尾节点数量的中间位置。对于长度为偶数或奇数的链表，中间节点的位置可能略有不同。以下是删除中间节点的基本步骤：

确定中间节点的位置：
- 可以使用快慢指针技术来找到中间节点。快指针每次移动两步，慢指针每次移动一步，当快指针到达链表尾部时，慢指针就在中间位置。
删除中间节点：
- 当找到了中间节点后，需要调整指针以跳过该节点。如果是单链表，需要让前一个节点指向当前中间节点的下一个节点。
- 如果是双链表，则只需要调整当前节点的前后指针即可。

删除 a/b 处的节点

删除 a/b 处的节点意味着要删除从头部开始的第 a/b * 链表长度的节点。这里的 a 和 b 是整数，并且 a < b。具体操作如下：

计算 a/b 处的位置：
- 首先遍历整个链表来获取链表的长度 N。
- 计算目标节点的位置 pos = ceil((a / b) * N)，这里 ceil 表示向上取整。
删除指定位置的节点：
- 再次遍历链表直到 pos-1 位置，这里的 pos 是计算得到的位置。
- 调整 pos-1 位置节点的 next 指针，使其指向 pos+1 位置的节点，从而跳过 pos 位置的节点。

注意：在实际编程中，你需要考虑边界条件，比如链表为空的情况，或者 a/b 导致的位置超出链表范围等。
以上描述的是算法上的逻辑，具体的实现会依赖于使用的编程语言和链表的具体实现方式

示例

接下来我会提供一些伪代码示例来帮助理解如何实现上述两种情况。请注意，这些示例将基于单向链表进行说明。

定义链表节点结构

首先定义一个简单的链表节点结构：

class ListNode:def __init__(self, value=0, next=None):self.value = valueself.next = next

删除中间节点

假设我们已经有一个链表 head，我们将使用快慢指针的方法来找到中间节点并删除它：

def delete_middle_node(head):if not head or not head.next:return Noneslow = headfast = headprev = None# 使用快慢指针找到中间节点while fast and fast.next:fast = fast.next.nextprev = slowslow = slow.next# 删除中间节点if prev:prev.next = slow.nextelse:  # 如果中间节点是头节点head = slow.nextreturn head

删除 a/b 处的节点

为了删除 a/b 处的节点，我们需要首先计算出确切的位置，然后找到该位置的前一个节点，并进行删除操作：

def delete_node_at_position(head, a, b):if not head or not head.next:return Nonelength = 0temp = head# 计算链表的长度while temp:length += 1temp = temp.next# 计算目标位置target_pos = int((a / b) * length)# 特殊情况处理if target_pos == 0:return head.nextcurrent = headcount = 0# 找到目标节点的前一个节点while current and count < target_pos - 1:current = current.nextcount += 1if current and current.next:current.next = current.next.nextreturn head

注意事项

这些函数返回了修改后的链表头节点。
在实际应用中，你可能需要根据具体需求调整边界条件处理。
delete_node_at_position 函数假设 a 和 b 是有效的输入，即 a 总是小于 b，并且 a / b 不会超过链表长度的比例。

Python 实现案例

下面是具体的 Python 实现案例，包括创建链表、删除中间节点以及删除 a/b 处节点的完整代码示例。

创建链表

首先，我们需要定义链表节点类，并编写一个函数来创建一个链表：

class ListNode:def __init__(self, value=0, next=None):self.value = valueself.next = nextdef create_linked_list(values):dummy_head = ListNode()current = dummy_headfor value in values:current.next = ListNode(value)current = current.nextreturn dummy_head.next

删除中间节点

接下来，我们实现删除中间节点的功能：

def delete_middle_node(head):if not head or not head.next:return Noneslow = headfast = headprev = None# 使用快慢指针找到中间节点while fast and fast.next:fast = fast.next.nextprev = slowslow = slow.next# 删除中间节点if prev:prev.next = slow.nextelse:  # 如果中间节点是头节点head = slow.nextreturn head

删除 a/b 处的节点

然后，实现删除 a/b 处节点的功能：

def delete_node_at_position(head, a, b):if not head or not head.next:return Nonelength = 0temp = head# 计算链表的长度while temp:length += 1temp = temp.next# 计算目标位置target_pos = int((a / b) * length)# 特殊情况处理if target_pos == 0:return head.nextcurrent = headcount = 0# 找到目标节点的前一个节点while current and count < target_pos - 1:current = current.nextcount += 1if current and current.next:current.next = current.next.nextreturn head

测试代码

最后，我们编写一个测试函数来验证这些功能：

def print_linked_list(head):current = headwhile current:print(current.value, end=" -> ")current = current.nextprint("None")# 创建一个示例链表
values = [1, 2, 3, 4, 5]
linked_list = create_linked_list(values)print("Original Linked List:")
print_linked_list(linked_list)# 删除中间节点
linked_list = delete_middle_node(linked_list)
print("Linked List after deleting middle node:")
print_linked_list(linked_list)# 删除 a/b 处的节点 (例如 a=1, b=2)
linked_list = delete_node_at_position(linked_list, 1, 2)
print("Linked List after deleting node at position 1/2:")
print_linked_list(linked_list)

这段代码将会创建一个包含 [1, 2, 3, 4, 5] 的链表，并演示如何删除中间节点以及删除 a/b 处的节点。你可以根据自己的需要调整 values 列表以及 a 和 b 的值来进行测试。

让我们继续通过具体的例子来测试删除中间节点和 a/b 处节点的功能。

示例代码完整版

以下是完整的 Python 代码示例，包括创建链表、删除中间节点、删除 a/b 处节点以及测试用例：

class ListNode:def __init__(self, value=0, next=None):self.value = valueself.next = nextdef create_linked_list(values):dummy_head = ListNode()current = dummy_headfor value in values:current.next = ListNode(value)current = current.nextreturn dummy_head.nextdef delete_middle_node(head):if not head or not head.next:return Noneslow = headfast = headprev = None# 使用快慢指针找到中间节点while fast and fast.next:fast = fast.next.nextprev = slowslow = slow.next# 删除中间节点if prev:prev.next = slow.nextelse:  # 如果中间节点是头节点head = slow.nextreturn headdef delete_node_at_position(head, a, b):if not head or not head.next:return Nonelength = 0temp = head# 计算链表的长度while temp:length += 1temp = temp.next# 计算目标位置target_pos = int((a / b) * length)# 特殊情况处理if target_pos == 0:return head.nextcurrent = headcount = 0# 找到目标节点的前一个节点while current and count < target_pos - 1:current = current.nextcount += 1if current and current.next:current.next = current.next.nextreturn headdef print_linked_list(head):current = headwhile current:print(current.value, end=" -> ")current = current.nextprint("None")# 创建一个示例链表
values = [1, 2, 3, 4, 5]
linked_list = create_linked_list(values)print("Original Linked List:")
print_linked_list(linked_list)# 删除中间节点
linked_list = delete_middle_node(linked_list)
print("Linked List after deleting middle node:")
print_linked_list(linked_list)# 删除 a/b 处的节点 (例如 a=1, b=2)
linked_list = delete_node_at_position(linked_list, 1, 2)
print("Linked List after deleting node at position 1/2:")
print_linked_list(linked_list)

测试输出

这段代码的预期输出如下：

Original Linked List:
1 -> 2 -> 3 -> 4 -> 5 -> None
Linked List after deleting middle node:
1 -> 2 -> 4 -> 5 -> None
Linked List after deleting node at position 1/2:
1 -> 4 -> 5 -> None

在这个例子中：