[数据结构与算法]剑指 Offer 24. 反转链表 【c++/java详细题解】

1、题目

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

示例:

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

限制：

• 0 <= 节点个数 <=5000

2、思路

(双指针，迭代) $(n)$

给定一个链表的头节点，让我们反转该链表并输出反转后链表的头节点。

样例：

如样例所示，原始链表为1->2->3->4->5->NULL，我们将其翻转输出5->4->3->2->1->NULL。下面我们来讲解双指针的做法。

将一个链表翻转，即将该链表所有节点的next指针指向它的前驱节点。由于是单链表，我们在遍历时并不能直接找到其前驱节点，因此我们需要定义一个指针保存其前驱节点。

每次翻转时，我们都需要修改当前节点的next指针，如果不在改变当前节点的next指针前保存其后继节点，那么我们就失去了当前节点和后序节点的联系，因此还需要额外定义一个指针用于保存当前节点的后继节点。

具体过程如下：

1、定义一个前驱指针pre和cur指针，pre指针用来指向前驱节点，cur指针用来遍历整个链表，初始化pre = null，cur = head。

2、我们首先保存cur指针指向节点的后继节点，然后让cur指针指向节点的next指针指向其前驱节点，即cur->next = pre。

3、pre指针和cur指针分别后移一位，重复上述过程，直到cur指向空节点。

4、最后我们返回pre节点。

图示过程如下：

时间复杂度分析： 只遍历一次链表，时间复杂度是$O(n)$。

3、c++代码

class Solution 
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *pre = NULL;
        ListNode *cur = head;
        while(cur)
        {
            ListNode *t = cur->next; //保留cur的后继节点
            cur->next = pre;         //cur指向其前驱节点
            pre = cur, cur = t;
        }
        return pre;                  //最后返回pre
    }
};

4、java代码

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null)
        {
            ListNode t = cur.next;  //保留cur的后继节点
            cur.next = pre;         //cur指向其前驱节点
            pre = cur;
            cur = t;
        }
        return pre;					//最后返回pre
    }
}

原题链接： 剑指 Offer 24. 反转链表