leetcode链表之删除链表结点
83、删除排序链表中的重复元素
文章出现的代码都是python3
题目
给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
示例1：
输入：head = [1,1,2]
输出：[1,2]
示例2：
输入：head = [1,1,2,3,3]
输出：[1,2,3]
思路
由于链表是已经排序好的，只需要判断当前结点的值是否和下一个结点的值是否相等，如果相等，删除下一个结点即可
代码：
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
if not head: return head
cur = head
while cur.next:
# 如果当前结点的值等于下一结点的值，直接将当前指针指向下下个结点
if cur.val == cur.next.val:
cur.next = cur.next.next
# 否则的话直接遍历即可
else:
cur = cur.next
return head
82、删除排序链表中的重复元素2
题目
给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
示例1：
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
示例2：
输入：head = [1,1,1,2,3]
输出：[2,3]
思路：
删除重复数字的节点，也就是需要重复数字的上一个结点，然后通过重复值进行迭代删除即可。
代码：
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
if not head: return head
# 由于删除结点的时候，可能会删除头结点，创建一个虚拟结点
cur = vHead = ListNode(0, head)
# 需要判断下个结点的值和下下个结点的值是否重复
while cur.next and cur.next.next:
if cur.next.val == cur.next.next.val:
# 临时变量存储，避免结点删除之后，值丢失的问题
temp = cur.next.val
# 遍历删除重复结点
while cur.next and cur.next.val == temp:
cur.next = cur.next.next
else:
cur = cur.next
return vHead.next
203、删除链表元素
题目
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例1：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
示例2：
输入：head = [], val = 1
输出：[]
示例3
输入：head = [7,7,7,7], val = 7
输出：[]
思路：
遍历比较元素大小，并删除
代码：
class Solution:
def removeElements(self, head: ListNode, val: int) -> ListNode:
if not head: return head
vHead = ListNode(0, head)
cur = vHead
while cur.next:
if cur.next.val == val:
cur.next = cur.next.next
else:
cur = cur.next
return vHead.next
237、删除链表中的结点
题目
请编写一个函数，用于 删除单链表中某个特定节点 。在设计函数时需要注意，你无法访问链表的头节点 head ，只能直接访问 要被删除的节点 。
题目数据保证需要删除的节点 不是末尾节点 。
示例1：
输入：head = [4,5,1,9], node = 5
输出：[4,1,9]
示例2：
输入：head = [4,5,1,9], node = 1
输出：[4,5,9]
示例3：
输入：head = [1,2,3,4], node = 3
输出：[1,2,4]
示例4：
输入：head = [0,1], node = 0
输出：[1]
示例5：
输入：head = [-3,5,-99], node = -3
输出：[5,-99]
思路：
按照一般思路，删除链表中的结点，一般会想到找结点的上一个结点进行删除，这道题没有给头结点以及上一个结点，所以这种方法行不通，并且删除的结点不是尾结点，也就是说我们可以将这个结点改成下一个结点，然后删除下一个结点就行。
代码：
class Solution:
def deleteNode(self, node):
node.val = node.next.val
node.next = node.next.next
移除重复结点
题目：
编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。
示例1：
输入：[1, 2, 3, 3, 2, 1]
输出：[1, 2, 3]
示例2：
输入：[1, 1, 1, 1, 2]
输出：[1, 2]
思路：
这道题和上面的不同点是链表未排序，可以使用hash表存储数据，然后判断已经出现则删除
代码：
class Solution:
def removeDuplicateNodes(self, head: ListNode) -> ListNode:
if not head or not head.next: return head
cur = ListNode(0, head)
seen = set()
# 判断下一个结点的值，这样有利于删除结点
while cur.next:
val = cur.next.val
if val in seen:
cur.next = cur.next.next
else:
seen.add(val)
cur = cur.next
return head
2095、删除链表的中间结点
题目：
给你一个链表的头节点 head 。删除 链表的 中间节点 ，并返回修改后的链表的头节点 head 。
长度为 n 链表的中间节点是从头数起第 ⌊n / 2⌋ 个节点（下标从 0 开始），其中 ⌊x⌋ 表示小于或等于 x 的最大整数。
- 对于 n = 1、2、3、4 和 5 的情况，中间节点的下标分别是 0、1、1、2 和 2 。
示例1：
输入：head = [1,3,4,7,1,2,6]
输出：[1,3,4,1,2,6]
示例2：
输入：head = [1,2,3,4]
输出：[1,2,4]
示例3：
输入：head = [2,1]
输出：[2]
思路
使用快慢指针找到中间结点的前置结点，删除掉中间结点
class Solution:
def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head: return head
# 慢节点指向虚拟头结点，这样在遍历的时候，慢节点就会指向中间结点的前置结点
slow = vhead = ListNode(0, head)
fast = head
# 使用快慢结点遍历，找到中间结点
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# 此时慢节点指向的是中间结点的前置结点，删除中间结点即可
slow.next = slow.next.next
return vhead.next
