单链表逆序

LeetCodee上有一道在线编程题,可以来这里试一试:https://leetcode-cn.com/problems/reverse-linked-list/

前向插入迭代法

该方式采用一次遍历链表,每次摘下一个节点。在原来节点空间的的基础上,采用前向插入法构建一条新链表————它就是逆序后的链表。

有一点要注意,rhead一定要初始化为nullptr,因为前向插入法的初始值将称为链表的尾部。

/**
* Reverse insertion list using forward insertion method
*/
ListNode* reverse_list(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}

ListNode* ptr = head, *rhead = nullptr; //init nullptr

while (ptr != nullptr){
ListNode* node = ptr->next;
ptr->next = rhead;
rhead = ptr;
ptr = node;
}

return rhead;
}

递归法

递归法依赖于栈不适合于长度较大的链表。用个例子说明基本原理:假设当前链表为A->B->C-D,当递归 弹栈head = B时,

  • 则需要将C->next = B
  • 同时,B->next = nullptr
/**
* Recursive method
*/
ListNode* reverse_list2(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}

ListNode* rhead = reverse_list2(head->next);

head->next->next = head;
head->next = nullptr;

return rhead;
}