题目描述

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

思路

使用三个指针遍历单链表，对每一个链接点的指针进行反转。

p 和 q 指针进行反向，用 r 记录下一个节点，然后从前往后一直进行。

原来的 head 变为尾指针，要令 head 的 next 指向 NULL。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == NULL || head->next == NULL)
        {
            return head;
        }
        ListNode *p = head, *r;
        ListNode *q = p->next;
        head->next = NULL;
        while(q != NULL)
        {
            r = q->next;
            q->next = p;
            p = q;
            q = r;
        }
        return p;
    }
};