0.牛客网刷题记录

1.BM1反转链表

1.1 解答

本题是不带头节点的链表反转。

三个节点，当前节点cur、当前节点前驱pre、用于保存‘当前’节点的临时temp。

循环条件：cur!=nullptr循环中：更新cur、pre、temp的顺序很重要！循环结束后：pre就是头节点

保存当前节点cur到temp，temp=cur
更新当前节点cur，cur=cur->next
更新当前节点temp的后继，temp->next=pre
更新当前节点temp的前驱pre，pre=temp

1.1.1 C++

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead==nullptr){
            return pHead;
        }
        ListNode* pre = nullptr;
        ListNode* temp = nullptr;
        while(pHead){
            temp = pHead;
            pHead = pHead->next;
            temp->next = pre;
            pre = temp;
        }
        return pre;
    }
};

1.2 拓展——单链表反转

1.2.1 迭代反转

该算法的实现思想非常直接，就是从当前链表的首元节点开始，一直遍历至链表的最后一个节点，这期间会逐个改变所遍历到的节点的指针域，令其指向前一个节点。具体的实现方法也很简单，借助 3 个指针即可。首先我们定义 3 个指针并分别命名为 beg、mid、end。它们的初始指向如下图所示：链表初始状态
在上图的基础上，遍历链表的过程就等价为：3 个指针每次各向后移动一个节点，直至 mid 指向链表中最后一个节点（此时 end 为 NULL ）。

需要注意的是，这 3 个指针每移动之前，都需要做一步操作，即改变 mid 所指节点的指针域，令其指向和 beg 相同。

在上图的基础上，我们先改变 mid 所指节点的指针域指向，另其和 beg 相同（即改为 NULL），然后再将 3 个指针整体各向后移动一个节点。整个过程如下图所示：

迭代反转链表过程一

在上图的基础上，先改变 mid 所指节点的指针域指向，令其和 beg 相同（指向节点 1 ），再将 3 个指针整体各向后移动一个节点。整个过程如下图所示：

迭代反转链表过程二

在上图的基础上，先改变 mid 所指节点的指针域指向，令其和 beg 相同（指向节点 2 ），再将 3 个指针整体各向后移动一个节点。整个过程如下图所示：
上图中，虽然 mid 指向了原链表最后一个节点，但显然整个反转的操作还差一步，即需要最后修改一次 mid 所指节点的指针域指向，令其和 beg 相同（指向节点 3）。如下图所示：

注意，这里只需改变 mid 所指节点的指向即可，不用修改 3 个指针的指向。

最后只需改变 head 头指针的指向，令其和 mid 同向，就实现了链表的反转。

//迭代反转法，head 为无头节点链表的头指针
link * iteration_reverse(link* head) {
    if (head == nullptr || head->next == nullptr) {
        return head;
    }
    else {
        link * beg = nullptr;
        link * mid = head;
        link * end = head->next;
        //一直遍历
        while (1)
        {
            //修改 mid 所指节点的指向
            mid->next = beg;
            //此时判断 end 是否为 NULL，如果成立则退出循环
            if (end == NULL) {
                break;
            }
            //整体向后移动 3 个指针
            beg = mid;
            mid = end;
            end = end->next;
        }
        //最后修改 head 头指针的指向
        head = mid;
        return head;
    }
}

1.2.2 头插法反转

头插法，在原有链表的基础上，依次将位于链表头部的节点摘下，然后采用从头部插入的方式生成一个新链表，则此链表即为原链表的反转版。

创建一个新的空链表，如下图所示：
从原链表中摘除头部节点 1，并以头部插入的方式将该节点添加到新链表中，如下图：
从原链表中摘除头部节点 2，以头部插入的方式将该节点添加到新链表中，如下图：
继续重复以上工作，先后将节点 3、4 从原链表中摘除，并以头部插入的方式添加到新链表中，如下图：

由此，就实现了对原链表的反转，新反转链表的头指针为 new_head。

link * head_reverse(link * head) {
    link * new_head = nullptr;
    link * temp = nullptr;  // 备份
    if (head == nullptr || head->next == nullptr) {
        return head;
    }
    while (head != nullptr)
    {
        temp = head;
        //将 temp 从 head 中摘除
        head = head->next;

        //将 temp 插入到 new_head 的头部
        temp->next = new_head;
        new_head = temp;
    }
    return new_head;
}

1.2.3 就地逆置反转

就地逆置法和头插法的实现思想类似，唯一的区别在于，头插法是通过建立一个新链表实现的，而就地逆置法则是直接对原链表做修改，从而实现将原链表反转。值得一提的是，在原链表的基础上做修改，需要额外借助 2 个指针（假设分别为 beg 和 end）。

初始状态下，令 beg 指向第一个节点，end 指向 beg->next，如下图所示：
将 end 所指节点 2 从链表上摘除，然后再添加至当前链表的头部。
将 end 指向 beg->next，然后将 end 所指节点 3 从链表摘除，再添加到当前链表的头部
将 end 指向 beg->next，再将 end 所示节点 4 从链表摘除，并添加到当前链表的头部

link * local_reverse(link * head) {
    if (head == nullptr || head->next == nullptr) {
        return head;
    }
    link * beg = nullptr;
    link * end = nullptr;
    beg = head;
    end = head->next;
    while (end != nullptr) {
        //将 end 从链表中摘除
        beg->next = end->next;
        //将 end 移动至链表头
        end->next = head;
        head = end;
        //调整 end 的指向，令其指向 beg 后的一个节点，为反转下一个节点做准备
        end = beg->next;
    }
    return head;
}

循环体中并没有涉及对beg本身的更新（只是对beg所指的物理实体的后继阈更新），也就是说beg的指向始终没变，但是end的指向有变化，head的指向也有变化。