链表-LC83删除链表的重复元素-简单-20210910
1. 题目描述
存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。
返回同样按升序排列的结果链表。
示例：
输入：head = [1,1,2]
输出：[1,2]
输入：head = [1,1,2,3,3]
输出：[1,2,3]
提示：
- 链表中节点数目在范围
[0, 300]内 -100 <= Node.val <= 100- 题目数据保证链表已经按升序排列
2. 题目解答
删除一个节点 node 的最常见方法是修改其前驱节点的 next 指针，使其指向之后的节点
2.1 尝试-利用哈希保存出现过的元素
忽略了链表有序这个性质
时间复杂度：
O
(
n
)
O(n)
O(n)，两次遍历，第一次遍历统计元素，第二次遍历检查元素
空间复杂度：
O
(
n
)
O(n)
O(n)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
res = []
dummy = ListNode(0, head)
p = dummy
while p.next: # 1.避免了空链表的情况 2.考虑了最后一个节点被删除的情况
if p.next.val in res:
p.next = p.next.next
else:
res.append(p.next.val)
p = p.next
return dummy.next
2.2 官方-一次遍历
思路：有序链表，重复元素位置是连续的
- cur \textit{cur} cur 指向链表的头节点，遍历如果当前$ \textit{cur} $与 cur.next \textit{cur.next} cur.next 对应的元素相同，那么将 cur.next \textit{cur.next} cur.next 从链表中移除；
- 否则说明链表中已经不存在其它与 $\textit{cur} $ 对应的元素相同的节点，因此可以将$ \textit{cur}$ 指向 cur.next \textit{cur.next} cur.next
- 返回链表的头节点
细节：
cur.next
\textit{cur.next}
cur.next为空节点，如果不加以判断，访问$ \textit{cur.next}$ 对应的元素会产生运行错误。因此只需要遍历到链表的最后一个节点，而不需要遍历完整个链表
时间复杂度：
O
(
n
)
O(n)
O(n)，n是链表的长度
空间复杂度：
O
(
1
)
O(1)
O(1)
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
2.3 双指针-不预处理出链表的长度
-
思路：快慢指针，用慢指针找到位置
使用两个指针【快慢指针】$ \textit{fast} 和 和 和 \textit{slow}$ 同时对链表进行遍历，并且 fast \textit{fast} fast 比$ \textit{slow}$ 超前 n 个节点。当$ \textit{fast}$ 遍历到链表的末尾时， slow \textit{slow} slow 就恰好处于倒数第 n n n 个节点- 所有节点依次入栈。
- 根据栈「先进后出」的原则，弹出栈的第 n 个节点就是需要删除的节点，并且目前栈顶的节点就是待删除节点的前驱节点。
- 修改链表结构，前驱节点的下个节点指向下个节点的下个节点【前驱节点.next = 前驱节点.next.next】
时间复杂度： O ( L ) O(L) O(L)，L是链表的长度
空间复杂度： O ( 1 ) O(1) O(1)
# 1.fast和slow都指向dummy
# 2.fast移动n次
# 3.两个一起移动；但是当slow指向倒数n的前驱节点是，fast在最后一个节点，所以判断fast.next为0为终止条件；或者一开始fast指向dummy.next
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
dummy = ListNode(0, head)
fast = dummy
slow = dummy
for i in range(n):
fast = fast.next
while fast.next:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy.next
# 改进
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
dummy = ListNode(0, head)
fast = dummy.next
slow = dummy
for i in range(n):
fast = fast.next
while fast:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy.next
3. 测试用例