LeetCode 206

一、问题描述

Description:

Reverse a singly linked list.

Hint: A linked list can be reversed either iteratively or recursively. Could you implement both?

二、解题报告

逆转一个单链表一般有 迭代 和 递归 两种方法。

1、迭代法

遍历该单链表，将节点一个一个摘下来，采用 头插法 插入另一条链表：

ListNode* reverseList(ListNode* head) {
    ListNode node(0);
    ListNode* L = &node;
    L->next = NULL;

    while(head!=NULL)
    {
        ListNode* q = head->next;
        head->next = L->next;
        L->next = head;  
        head = q;
    }

    return L->next;
}

2、递归法

如果只有一个节点，直接返回。否则，将当前链表 a1,a2,...an 的子链表 a2,...an 进行逆转，返回逆转后的第一个节点的指针，再将 a1 节点加到 a2 节点后面。

ListNode* reverseList(ListNode* head) {
    if(head==NULL || head->next==NULL)
        return head;

    ListNode* q = head->next;
    ListNode* new_head = reverseList(q);
    head->next = NULL;
    q->next = head;

    return new_head;
}

LeetCode答案源代码：https://github.com/SongLee24/LeetCode