题目内容:一个单链表L=(a1 , a2 , … , an-1 , an),其逆单链表定义为L’=( an , an-1 , … , a2 , a1),编写算法将单链表L逆置,要求逆单链表仍占用原单链表的空间。 输入格式:一行内输入原单链表中的数据(若干个正整数,之间用空格隔开,并以-1结束) 输出格式:一行内输出建立的原单链表数据结果,之间用两个分隔符 -- 隔开,结束标志-1不输出。 下一行内输出逆置后的单链表数据结果,之间用两个分隔符 -- 隔开。 输入样例:2 4 6 8 10 -1 输出样例:--2--4--6--8--10 --10--8--6--4--2
时间: 2024-01-12 15:03:08 浏览: 25
以下是实现该算法的Python代码:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_linked_list(head: ListNode) -> ListNode:
prev, curr = None, head
while curr:
curr.next, prev, curr = prev, curr, curr.next
return prev
# 输入原单链表数据
inputs = list(map(int, input().split()))[:-1]
# 建立原单链表
dummy = ListNode()
tail = dummy
for val in inputs:
tail.next = ListNode(val)
tail = tail.next
head = dummy.next
# 输出原单链表数据
while head:
print('--', head.val, end='')
head = head.next
print()
# 逆置单链表
new_head = reverse_linked_list(dummy.next)
# 输出逆置后的单链表数据
while new_head:
print('--', new_head.val, end='')
new_head = new_head.next
print()
```
其中,`reverse_linked_list` 函数实现了单链表的逆置操作,它接受一个链表头结点作为输入,返回逆置后的链表头结点。建立原单链表的部分使用了哑结点(dummy node)技巧,最后将其丢弃即可。