Python实现单链表中元素的反转

下面是Python实现单链表中元素反转的攻略。

1. 创建单链表

首先，我们需要定义单链表的结构。单链表可以通过定义一个节点类来实现，该类至少包含两个属性，一个是存储数据的值，一个是指向下一个节点的指针。具体实现如下：

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

接下来，我们定义一个函数来创建单链表。该函数需要从列表中读取数据并将其存储到链表中。下面是函数的具体实现：

def createLinkedList(data):
    if len(data) == 0:
        return None
    head = ListNode(data[0])
    node = head
    for i in range(1, len(data)):
        node.next = ListNode(data[i])
        node = node.next
    return head

2. 反转链表

接下来，我们需要实现链表反转的函数。这个函数的具体实现可以分为三个步骤：

1. 初始化三个指针pre、cur、nxt。初始化pre指针为None，cur指针为链表头节点，nxt指针为链表头节点的下一个节点。
2. 将cur的next指针指向pre。
3. 将pre、cur、nxt三个指针分别向右移动一个节点，即令pre=cur，cur=nxt，nxt=nxt.next。如果nxt非空，返回第二步；否则，返回pre。

下面是反转链表函数的具体实现：

def reverseLinkedList(head):
    pre = None
    cur = head
    nxt = head.next
    while nxt != None:
        cur.next = pre
        pre = cur
        cur = nxt
        nxt = nxt.next
    cur.next = pre
    return cur

3. 测试代码

接下来，我们来测试一下我们的代码是否能够正确反转链表。下面是两个测试用例:

# Test case 1
data = [1, 2, 3, 4, 5]
head = createLinkedList(data)
print("Original linked list:", head.val, head.next.val, head.next.next.val, head.next.next.next.val, head.next.next.next.next.val)
head = reverseLinkedList(head)
print("Reversed linked list:", head.val, head.next.val, head.next.next.val, head.next.next.next.val, head.next.next.next.next.val)

# Test case 2
data = [3, 2, 1]
head = createLinkedList(data)
print("Original linked list:", head.val, head.next.val, head.next.next.val)
head = reverseLinkedList(head)
print("Reversed linked list:", head.val, head.next.val, head.next.next.val)

输出结果：

Original linked list: 1 2 3 4 5
Reversed linked list: 5 4 3 2 1
Original linked list: 3 2 1
Reversed linked list: 1 2 3

可以看到，我们的代码成功地将链表进行了反转，并输出了正确的结果。

希望这个攻略能够帮助到您。

阅读剩余 40%