链表反转

[编程题]链表反转

热度指数：539 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

链表反转： 1->2->3->4->5 通过反转后成为5->4->3->2->1。说明算法的复杂度。

输入描述:

第一行一个正整数n(1<=n<=100000)

第二行n个正整数a1,a2,...,an(1 <= ai <=100000)，表示链表顺序的结点值。

输出描述:

输出一行，n个数，表示反转后链表依次的结点值。

示例1

输入

10
9 10 6 6 8 7 5 7 7 5

输出

5 7 7 5 7 8 6 6 10 9

算法知识视频讲解

Python

gapex

Python3，n没用

class Node:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next


n = int(input())
nums = input().split()
head = Node('head')
tail = head
for num in nums:
    node = Node(num)
    tail.next = node
    tail = node


def inverse(head: Node) -> Node:
    '''给定链表第一个有效节点，反转单链表'''
    if head is None or head.next is None:
        return
    prev, curr, next = None, head, None
    while curr is not None:
        next = curr.next
        curr.next = prev
        prev = curr
        curr = next
    return prev


tail = head.next
head.next = inverse(head.next)
node = head.next
while node is not tail:
    print(node.val, end=' ')
    node = node.next
else:
    assert tail.val == node.val
    print(tail.val, end='')

发表于 2019-11-26 15:34:46 回复(0)