剑指Offer第15题：反转链表

发表于 更新于 分类于

题目：输入一个链表，反转链表后，输出新链表的表头。
解题思路：定义一个指针rev用于存储反转过的头结点，p用于指向还未反转的头结点，tmp指针用于存储p的下一结点。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
ListNode* ReverseList(ListNode* pHead) {
    ListNode* rev = NULL; //初始时为空
    ListNode* p = pHead; //初始时，所有的结点都未被反转
    ListNode* tmp; 
    while (p) {
        tmp = p -> next; //先存储p的下一结点，因为下一步要改变p的下一结点的指向
        p -> next = rev; //p的下一结点指向已经反转好的头结点
        rev = p; //rev的结点移向最新的反转过的结点p
        p = tmp; //p移向下一未反转的结点
    }
    return rev;
}