LinkedList(链表)是一种线性数据结构,由一系列节点组成,每个节点包含数据部分和指向下一个节点的指针(在双向链表中还有指向前一个节点的指针)。反转链表是指将链表的节点顺序完全倒置。
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode current = head;
ListNode next = null;
while (current != null) {
next = current.next; // 保存下一个节点
current.next = prev; // 反转当前节点的指针
prev = current; // 移动prev指针
current = next; // 移动current指针
}
return prev; // prev现在是新的头节点
}
def reverseList(head):
if not head or not head.next:
return head
reversed_head = reverseList(head.next)
head.next.next = head # 反转指针方向
head.next = None # 断开原指针
return reversed_head
// 错误的反转实现
function reverseList(head) {
let prev = null;
let current = head;
while (current) {
current.next = prev; // 直接修改next指针,丢失了原next节点
prev = current;
current = current.next; // current已经是prev了,导致无限循环
}
return prev;
}
修复方法:在修改next指针前,先保存下一个节点的引用
// 未考虑空链表情况
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode* prev = NULL;
struct ListNode* curr = head;
struct ListNode* next = NULL;
while (curr != NULL) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev; // 如果head为NULL,返回NULL
}
虽然这个实现实际上能处理空链表,但很多初学者会忘记考虑这种边界情况。
链表反转常用于:
通过正确实现反转算法并注意上述常见问题,应该能解决链表反转不按预期工作的问题。
没有搜到相关的文章