链表反转是数据结构的基本功,主要有递归和非递归两种实现方式。我们一一介绍如下:
1. 非递归实现主要包括如下4步: 1)如果head为空,或者只有head这一个节点,return head即可; 2)从头到尾遍历链表,把reversedHead赋值给当前节点的next; 3)当前节点赋值给reversedHead; 4)遍历结束,return reversedHead。
下图试图来辅助说明: 代码如下:
node* reverseList(node* head)
{
if(head == NULL || head->next == NULL)
return head;
node* reversedHead = NULL;
node* p = head;
while(p != NULL)
{
node* q = p;
q->next = reversedHead;
reversedHead = q;
p = p->next;
}
return reversedHead;
}
2. 递归实现递归的实现方式主要有4步: 1)如果head为空,或者只有head这一个节点,return head即可; 2)先遍历head->next为首的链表,得到一个头结点newHead; 3)把head赋值给head->next->next, head->next为空; 4)返回newHead。
下图也说明了上述步骤:
代码实现如下:
node* reverseList2(node* head)
{
if(head == NULL || head->next == NULL)
return head;
node* newHead = reversedList2(head->next);
head->next->next = head;
head->next = NULL;
return newHead;
}
|
|
来自: 光之翼Jerryhc > 《文件夹1》