3558: 链表逆置(选做)

Question

3558: 链表逆置(选做)
内存限制：128 MB
时间限制：1.000 S
评测方式：普通裁判
命题人：syuao
提交：77
解决：16
题目描述
给定一个无头结点单链表的头结点指针pHead, 编写函数，实现该链表的逆置： 假设原有链表 1 -> 2 ->3 ->4 ->5 运行函数后， 5 -> 4 ->3 ->2 ->1
输入
一批整数
输出
逆置出来的这批整数
样例输入 复制
3 7 2 5 1 4 8 9 2
样例输出 复制
2 9 8 4 1 5 2 7 3
提示
使用单链表实现

Answer 1

让阿豪来帮你解答，本回答参考chatgpt3.5编写提供，如果还有疑问可以评论或留言

## 问题解析 本题要求实现一个函数来逆置一个无头节点的单链表。单链表是一种数据结构，其中每个节点包含一个数据部分和一个指向下一个节点的指针。逆置操作的目标是将链表的顺序反转。

输入输出格式

• 输入：一批整数，表示单链表的节点值，输入结束符为文件结束（EOF）。
• 输出：逆置后的单链表节点值，按空格分隔。

示例

样例输入:

3 7 2 5 1 4 8 9 2

样例输出:

2 9 8 4 1 5 2 7 3

解题思路

我们可以使用一个简单的迭代方法来逆置链表。主要思路是维护三个指针： 1. prev：指向当前节点的前一个节点。 2. current：指向当前正在处理的节点。 3. next：指向当前节点的下一个节点。

具体步骤

1. 初始化prev为NULL，current为链表的头节点。
2. 迭代遍历链表，依次更新每个节点的指向，把current.next指向prev，使指针反向。
3. 更新prev和current，依次向前移动。
4. 当当前节点遍历结束，prev将指向新的头节点。
5. 返回新的头节点。

实现代码

下面是实现链表逆置的Python代码示例：

class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next
def reverse_linked_list(head):
    prev = None
    current = head
    while current:
        next_temp = current.next  # 保存当前节点的下一个节点
        current.next = prev       # 反转节点的指向
        prev = current            # 移动 prev 到当前节点
        current = next_temp       # 移动到下一个节点
    return prev  # 返回新的头节点
def print_linked_list(head):
    current = head
    values = []
    while current:
        values.append(current.value)
        current = current.next
    print(" ".join(map(str, values)))
def main():
    import sys
    # 输入链表节点
    head = None
    tail = None
    for line in sys.stdin:
        values = list(map(int, line.split()))
        for value in values:
            new_node = ListNode(value)
            if head is None:
                head = new_node
            else:
                tail.next = new_node
            tail = new_node
            
    # 逆置链表
    reversed_head = reverse_linked_list(head)
    
    # 输出结果
    print_linked_list(reversed_head)
if __name__ == "__main__":
    main()

代码说明

1. ListNode类定义了链表节点，包含节点值和指向下一个节点的指针。
2. reverse_linked_list函数实现链表的逆置逻辑。
3. print_linked_list函数打印链表中的所有节点值。
4. main函数处理输入，创建链表，调用逆置函数，最后输出逆置后的链表。

复杂度分析

• 时间复杂度：O(n)，其中n是链表的节点数。我们遍历链表一次。
• 空间复杂度：O(1)，仅使用了固定数量的额外空间。 通过以上步骤和代码实现，可以成功逆置输入的单链表，并输出结果。