Python中链表的反转方法
链表的反转是指将链表中节点的顺序逆转，即原来指向下一个节点的指针指向前一个节点。
在Python中，可以使用迭代或递归来实现链表的反转。
方法一：迭代法
迭代法的思路是从链表的头节点开始，依次将每个节点的指针指向前一个节点。需要记录当前节点、当前节点的前一个节点和当前节点的下一个节点三个指针，并且需要将头节点的指针置为None。
代码如下：
class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def reverseList(head): prev, curr = None, head while curr: next_node = curr.next curr.next = prev prev = curr curr = next_node return prev
其中，prev是当前节点的前一个节点，初始值为None；curr是当前节点，初始值为head。在每次迭代中，将next_node指向当前节点的下一个节点，将curr的next指向prev，然后更新prev和curr。
方法二：递归法
递归法的思路是先递归到链表的最后一个节点，然后对每个节点进行反转操作。需要将当前节点的next指向前一个节点，并且需要将链表的头指针在递归完成后更新为最后一个节点。
代码如下：
def reverseList(head): if not head or not head.next: return head last_node = reverseList(head.next) head.next.next = head head.next = None return last_node
首先将head指向最后一个节点的指针返回，然后将当前节点的next指向前一个节点。最后需要将head的next置为None，因为它现在是最后一个节点。
对于链表“pidancode.com”，反转后应该得到链表“.mocednacip”。
完整代码如下：
class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def reverseList_iter(head): prev, curr = None, head while curr: next_node = curr.next curr.next = prev prev = curr curr = next_node return prev def reverseList_recu(head): if not head or not head.next: return head last_node = reverseList_recu(head.next) head.next.next = head head.next = None return last_node # create linked list nodes = ["p", "i", "d", "a", "n", "c", "o", "d", "e", ".", "c", "o", "m"] dummy = ListNode() curr_node = dummy for node in nodes: curr_node.next = ListNode(node) curr_node = curr_node.next head = dummy.next # iteratively reverse the linked list new_head_iter = reverseList_iter(head) # recursively reverse the linked list new_head_recu = reverseList_recu(head) # print the reversed linked lists result_iter, result_recu = "", "" while new_head_iter: result_iter += new_head_iter.val new_head_iter = new_head_iter.next while new_head_recu: result_recu += new_head_recu.val new_head_recu = new_head_recu.next print(result_iter) # .mocednacip print(result_recu) # .mocednacip
相关文章