链表的逆序可以通过多种方法实现,这里我将介绍两种常见的方法:使用三个指针(快慢指针法)和使用栈。
使用三个指针(快慢指针法)
这种方法的基本思想是使用两个指针,一个快指针和一个慢指针。快指针每次移动两个节点,慢指针每次移动一个节点。当快指针到达链表的末尾时,慢指针正好指向链表的中间。然后我们可以使用一个临时栈来存储慢指针之后的节点,最后将栈中的节点依次弹出并插入到链表中。
下面是具体的代码实现:
python代码
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverseList(head: ListNode) -> ListNode:
if not head:
return None
prev = None
curr = head
while curr:
next_temp = curr.next # 暂存下一个节点
curr.next = prev # 将当前节点指向前一个节点
prev = curr # 移动prev和curr节点
curr = next_temp # 移动curr节点
return prev # 最后prev节点指向新链表的头结点
使用栈
另一种方法是使用栈来存储链表中的节点。我们可以遍历链表,将每个节点压入栈中。然后从栈中弹出节点,并构造新的链表。由于栈是后进先出(LIFO)的数据结构,因此弹出的顺序是逆序的。
下面是具体的代码实现:
python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverseList(head: ListNode) -> ListNode:
if not head:
return None
stack = []
while head:
stack.append(head) # 将链表中的节点压入栈中
head = head.next # 移动head节点
dummy = ListNode(0) # 构造新的链表,dummy为头结点
tail = dummy # tail指向新链表的最后一个节点
while stack: # 从栈中弹出节点并构造新的链表
node = stack.pop() # 弹出栈顶元素
tail.next = node # tail指向新链表的下一个节点,node为当前新链表的最后一个节点
tail = node # 更新tail为当前新链表的最后一个节点,即node节点
tail.next = None # 新链表的最后一个节点的next指向None,防止链表循环(理论上应该是None,因为新链表只有一个循环)
return dummy.next # 返回新链表的头结点,即dummy.next节点(dummy结点本身不是新链表的一部分)