【问题描述】请根据输入的逆序数据采用头插法创建一个单链表,然后删除相同的数据,仅保留一个。 【输入形式】逆序的数据,数据0代表输入结束 【输出形式】创建成功的原始单链表的数据,以及删除某些元素后的单链表的数据,其中相同数据仅保留一个 【样例输入】 9 9 8 8 7 6 5 5 4 0 【样例输出】 4 5 5 6 7 8 8 9 9 4 5 6 7 8 9
时间: 2024-01-01 11:07:02 浏览: 77
创建单链表,逆序输入
以下是实现代码(Python):
```python
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def create_linked_list(nums):
dummy = ListNode(0)
for num in nums:
node = ListNode(num)
node.next = dummy.next
dummy.next = node
return dummy.next
def remove_duplicates(head):
if not head:
return head
p = head
while p.next:
if p.val == p.next.val:
p.next = p.next.next
else:
p = p.next
return head
# 输入数据
nums = []
while True:
num = int(input())
if num == 0:
break
nums.append(num)
# 创建原始单链表
head = create_linked_list(nums)
# 输出原始单链表的数据
while head:
print(head.val, end=' ')
head = head.next
print()
# 删除相同数据,仅保留一个
head = remove_duplicates(head)
# 输出删除相同数据后的单链表的数据
while head:
print(head.val, end=' ')
head = head.next
print()
```
以下是代码的说明:
1. 定义一个 `ListNode` 类,表示单链表的节点。每个节点包含两个属性,一个是节点的值,一个是指向下一个节点的指针。
2. 定义 `create_linked_list` 函数,根据输入的逆序数据采用头插法创建一个单链表,并返回链表的头节点。
3. 定义 `remove_duplicates` 函数,删除相同数据,仅保留一个,并返回链表的头节点。
4. 读入输入的数据,创建原始单链表,并输出原始单链表的数据。
5. 删除相同数据,仅保留一个,输出删除相同数据后的单链表的数据。
在这个代码中,我们通过头插法创建单链表。头插法比较简单,就是先创建一个空的头节点 `dummy`,然后依次把输入的数据转化成节点,并插入到头节点之后。由于是逆序输入的数据,所以插入的顺序就是正序的。
删除相同数据的算法也比较简单,我们只需要维护一个指针 `p`,从头节点开始遍历单链表,如果 `p` 节点的值等于 `p.next` 节点的值,说明有重复的数据,直接删除 `p.next` 节点,然后继续遍历;否则,将指针 `p` 移动到下一个节点,继续遍历。
阅读全文