如何在链表中删除结点

在链表中删除节点的方法有多种。以下是两种常见的方法：

1. 删除指定位置的节点：首先，需要遍历链表，找到要删除的节点的前一个节点。然后，使前一个节点的next指针指向要删除节点的下一个节点，这样就将要删除的节点从链表中移除了。最后，释放被删除节点的内存空间。
代码示例：

   Node *p, *prev;
   int pos = 3; // 假设要删除的位置是3
   int count = 1;
   
   for (p = head, prev = NULL; p != NULL && count < pos; count++) {
       prev = p;
       p = p->next;
   }
   
   if (p != NULL) {
       if (prev != NULL) {
           prev->next = p->next;
       } else {
           head = p->next;
       }
       
       free(p);
   }

2. 删除指定值的节点：同样需要遍历链表，找到要删除的节点。如果找到了与给定值相等的节点，则将其从链表中删除。

相关问题

删除双向链表中的重复结点

要删除双向链表中的重复节点，可以使用哈希表记录已经出现的节点值，然后遍历链表，如果当前节点的值已经在哈希表中出现过了，就将该节点从链表中删除。以下是代码实现：

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

def delete_duplicates(head: ListNode) -> ListNode:
    if not head:
        return head

    visited = set()
    visited.add(head.val)

    curr = head.next
    while curr:
        if curr.val in visited:
            prev = curr.prev
            prev.next = curr.next
            if curr.next:
                curr.next.prev = prev
        else:
            visited.add(curr.val)
        curr = curr.next

    return head

在这个算法中，我们首先创建一个哈希表 `visited`，用来记录已经出现的节点值。我们遍历链表，如果当前节点的值已经在哈希表中出现过了，就将该节点从链表中删除。否则，将当前节点的值添加到哈希表中。

这个算法的时间复杂度为 $O(n)$，其中 $n$ 是链表中节点的数量。空间复杂度也为 $O(n)$，因为我们需要使用哈希表来记录已经出现的节点值。

删除循环链表中结点s的前驱结点

由于循环链表中每个结点都有前驱结点，因此删除结点s的前驱结点需要考虑两种情况。

情况一：当s是链表的第一个结点时，需要删除的是链表的最后一个结点，即链表中的尾结点。此时，需要先找到链表的尾结点，然后将其指向s的后继结点，即可完成删除操作。

情况二：当s不是链表的第一个结点时，只需将s的前驱结点的指针指向s的后继结点即可完成删除操作。

具体实现代码如下：

if(s == head) { //情况一
    ListNode *tail = head;
    while(tail->next != head) {
        tail = tail->next;
    }
    tail->next = s->next;
} else { //情况二
    ListNode *pre = head, *cur = head->next;
    while(cur != s) {
        pre = cur;
        cur = cur->next;
    }
    pre->next = cur->next;
}