【leetcode C语言实现】剑指 Offer 24. 反转链

题目描述

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

示例:

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

限制：

0 <= 节点个数 <= 5000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof

解题思路

对链表进行反转就是让遍历到的节点指向前一个节点，但是在改变当前节点指针指向之前需要保留下下一个节点的信息，否则当前节点的下一个节点会丢失。需要考虑的边界条件：

1. 链表为空
2. 链表只有一个节点

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* reverseList(struct ListNode* head){
    struct ListNode *pnode = head;
    struct ListNode *phead = NULL;
    struct ListNode *pre = NULL;
    struct ListNode *pnext = NULL;

    while(pnode)
    {
        pnext = pnode->next;
        if(!pnext)
            phead = pnode;

        pnode->next = pre;
        pre = pnode;
        pnode = pnext;
    }

    return phead;
}

执行结果

时间复杂度：O(n)，空间复杂度：O(1)