单链表反转-算法题0001

笔记

  单链表反转最正规的解法是牛客网的官方解法的方法二。时间复杂度O(N),空间复杂度O(1)。第一遍读解法晕头转向，自己梳理了一遍，将重点用红字批注出来。

题想考察的是：如何调整链表指针，来达到反转链表的目的。
初始化：3个指针
1）pre指针指向已经反转好的链表的最后 一个首节点，最开始没有反转 翻转后的链表还为空，所以指向nullptr
2）cur指针指向待反转链表的第一个 当前节点，最开始第一个节点待反转，所以指向head
3）nex指针指向待反转链表的第二个 下一个节点，目的是保存链表，因为cur改变指向后，后面的链表则失效了，所以需要保存
接下来，循环执行以下三个操作
1）nex = cur->next, 保存作用
2）cur->next = pre 这一步实际上两个内容，其一是从待翻转链表首结点拆出一个元素，其二是将这个元素作为翻转后链表的头，和上一步已经翻转好的链表拼接起来。
3）pre = cur， 更新已经反转好的链表的首节点
4）cur = nex; 指针后移，操作下一个未反转链表的第一个节点
循环条件，当然是cur != nullptr
循环结束后，cur当然为nullptr，所以返回pre，即为反转后的头结点

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

/**
 * 
 * @param pHead ListNode类 
 * @return ListNode类
 */
struct ListNode* ReverseList(struct ListNode* pHead ) {
    // write code here
    if(pHead == NULL) return NULL;

    struct ListNode* Pre = NULL;//存新构建链表的首，这一步不好想
    struct ListNode* Cur = pHead;
    struct ListNode* Nex = NULL;
	// 把握一个主线就是 如何动态的构建翻转后的链表	
    while(Cur!=NULL)
    {
        Nex=Cur->next;// A 移动指针指向下一个元素
        //{{完成pre指针指向反转后链表的首，
        Cur->next = Pre;//核心1 当前节点的下一个指向旧链表的首部
        Pre = Cur;//核心2 pre指针指向上一步构建好的反转后链表的首部
        //}}
        Cur = Nex;// A 移动指针指向下一个元素
    } 
    return Pre;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31