LeetCode #206：Reverse Linked List(反转单链表)

题目描述

学过链表的应该都会写，但是这个题有个坑就是链表的头结点是存放数据的，这与大部分数据结构教材不同（我以为头结点不存放数据结果死活过不了）。和题解不同的是我手动给它安了一个不存放数据的头结点运用头插法。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == NULL || head->next == NULL) 
            return head; //链表中只有一个元素或为空时直接返回头结点
        
        ListNode* pHead = new ListNode(0, head); //由于本题头结点不为空，这里我手动给它加一个头结点，用头插法反转链表
        ListNode* p = NULL;
        ListNode* q = NULL;
        p = pHead->next;
        q = p->next;
        pHead->next = NULL;
        while(p != NULL) {
            p->next = pHead->next;
            pHead->next = p;
            p = q;
            if (q != NULL)
                q = q->next; //若不用if判断则到p指向最后一个结点的时候会空指针报错
        }

        return pHead->next; //由于手动安了个头结点故返回时要返回头结点的后继
    }
};

题解的方法：

ListNode* reverseList(ListNode* head) {
    ListNode* pre = NULL;
    ListNode* cur = head;

    while(cur != NULL) {
        ListNode* post = cur->next;
        cur->next = pre;
        pre = cur;
        cur = post;
    }

    return pre;
}