LeetCode（206） Reverse Linked List

题目

Reverse a singly linked list.

click to show more hints.

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

分析

反转链表。

一个简单的解法，既然反转该链表，我们把所有节点作为一个输入序列，按照头插法重新构造一个链表即可，它既是所给链表的反转结果。

题目所给提示还有另外两种方法解决，迭代和递归。

没有想到所说的迭代是个什么意思，下面将给出头插法和递归实现的代码！

AC代码

class Solution {
public:
    //方法一：头插法
    ListNode* reverseList(ListNode* head) {
        if (head == NULL)
            return head;

        //反转，即将所有节点按照头插法重新插入一遍即可
        ListNode *p = head->next;
        head->next = NULL;
        while (p)
        {
            //保存p的后续节点
            ListNode *r = p->next;
            p->next = head;
            head = p;
            p = r;
        }
        return head;
    }

    //方法二：递归实现
    ListNode* reverseList2(ListNode* head) {
        if (head == NULL)
            return head;

        ListNode *p = head;

        //反转其余节点组成的链表，将头结点链接到尾部
        if (head->next)
        {
            head = reverseList(head->next);
            ListNode *r = head;
            while (r->next)
                r = r->next;
            r->next = p;
        }           
        p->next = NULL;
        return head;
    }
};

GitHub测试程序源码