题目描述

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:

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

限制：

0 <= 节点个数 <= 5000

无头结点(两种方式)

C ++ 代码1

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *curr = head, *pre = NULL;//curr指向当前结点,pre指向上一个结点
        while(curr != NULL){//已暗含空指针的判断
            ListNode *tmp = curr -> next;//tmp指向下一个结点
            curr -> next = pre;//当前结点的链域指向前一个结点
            pre = curr;//pre指针后移
            curr = tmp;//当前指针后移
        }
        return pre;
    }
};

C ++ 代码2

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == NULL) return head;//若为空指针则之间返回，不能少判断
        ListNode *p, *r;
        p = head -> next;//p指向第二个元素结点
        head -> next = NULL;//处理第一个元素结点
        while(p != NULL){//从第二个元素结点开始处理
            r = p -> next;//r暂存p后一个结点
            p -> next = head;//当前结点的链域指向前一个结点
            head = p;//head指针后移
            p = r;//p指针后移
        }
        return head;
    }
};

例题

反转链表

有头结点(两种方式)

C ++ 代码1

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *pre, *p = head -> next, *r = p -> next;//p指向当前所处理的结点
        p -> next = NULL;//处理第一个结点
        while( r != NULL){//从第二个结点开始
            pre = p;//pre指向当前已处理好的结点
            p = r;//p指针后移一位
            r = r -> next;//r指针后移一位
            p -> next = pre;//p的链域指向前一个结点
        }
        head -> next = p;//将头指针的链域指向
        return head;
    }
};

C ++ 代码2

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == NULL) return head;
        ListNode *p, *r;
        p = head -> next;//p指向第一个元素结点
        head -> next = NULL;//处理头结点
        while(p != NULL){//从第一个元素结点开始处理
            r = p -> next;//r暂存p后一个结点
            p -> next = head -> next;//当前结点的链域指向前一个结点
            head -> next = p;//head指针后移
            p = r;//p指针后移
        }
        return head;
    }
};