【算法专题训练】16、反转链表

1、单链表特点：

• 单链表最大的特点就是其单向性，只能顺着指向下一个节点的指针方向从头到尾遍历链表而不能反方向遍历。
• 所以要查询链表的末尾节点数据，需要从头开始遍历到指定位置。

2、LCR 024. 反转链表

题目信息：

• https://leetcode.cn/problems/UHnkqh/description/

给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。

示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：
输入：head = [1,2]
输出：[2,1]

示例 3：
输入：head = []
输出：[]

提示：
链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000
进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

解题思路：

• 审题：输入一个链表，要求将该链表的结点进行翻转，并最终返回翻转后的链表头结点
• 使用三个指针变量来实现，prev，curr，next
• prev用于记录翻转后的链表的头结点，也就是原始链表操作的前一个结点位置
• curr用于记录当前操作的指针，next指针用于记录当前操作指针curr的下一个指针结点
• 在curr操作的时候，需要先使用next指针记录curr的下一个指针位置，因为接下来的处理逻辑是将curr的指针域指向prev
• 如果没有next指针记录着，则链表就会断开了，而prev也需要重新赋值为curr指针，这样prev就一直是翻转后链表的头结点位置
• 链表翻转后是在原有的链表节点上重新指向，没有使用额外的数据存储

代码实现：

ListNode *reverseList(ListNode *head)
{
    ListNode *prev = nullptr;
    ListNode *curr = head;
    ListNode *next = nullptr;
    while(curr != nullprt){
        // 先记录下一个节点的位置
        next = curr->next;
        // 当前结点的指针域，指向翻转后的头结点prev
        curr->next = prev;
        // 翻转后的头结点重新赋值为新的头结点
        prev = curr;
        // 剩下的链表指针继续遍历，curr指针后移
        curr = next;
    }
    return prev;
}

3、LCR 025. 两数相加 II

题目信息：

• https://leetcode.cn/problems/lMSNwu/description/

给定两个 非空链表 l1和 l2 来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
可以假设除了数字 0 之外，这两个数字都不会以零开头。

示例 1：
输入：l1 = [7,2,4,3], l2 = [5,6,4]
输出：[7,8,0,7]

示例 2：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[8,0,7]

示例 3：
输入：l1 = [0], l2 = [0]
输出：[0]

提示：
链表的长度范围为 [1, 100]
0 <= node.val <= 9
输入数据保证链表代表的数字无前导 0

进阶：如果输入链表不能修改该如何处理？换句话说，不能对列表中的节点进行翻转。

解题思路：

• 1、审题：输入两个链表，链表整体表示一个非负整数，链表的每个结点为单独的一个数字，现在要将表示数字的链表进行相加处理，并返回操作后的链表头结点
• 2、解题：翻转链表解法
• 将两个链表都进行翻转，同时遍历两个链表，获取到同样位置的链表节点
• 对链表节点中的数字，进行加法操作，并将加法操作后的结果插入到新链表中，
• 遍历过程中会遇到其中一个链表的结点为null则返回数组0进行加法操作
• 注意两数相加产生的进位数字

代码实现：

ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
{
    ListNode *dummy = new ListNode(); // 哨兵节点

    // 对l1，l2链表进行翻转操作
    ListNode *newL1 = reverseList(l1);
    ListNode *newL2 = reverseList(l2);
    int spac = 0; // 进位

    // 遍历链表的结点
    while (newL1 != nullptr || newL2 != nullptr)
    {
        // 获取当前链表结点的数字
        int num1 = (newL1 != nullptr ? newL1->val : 0);
        int num2 = (newL2 != nullptr ? newL2->val : 0);

        int sum = num1 + num2 + spac;
        spac = sum / 10; // 进位获取
        sum = (sum >= 10 ? sum % 10 : sum);

        ListNode *newNode = new ListNode(sum);
        // 链表插入到哨兵节点后面
        newNode->next = dummy->next;
        dummy->next = newNode;

        newL1 = newL1 != nullptr ? newL1->next : nullptr;
        newL2 = newL2 != nullptr ? newL2->next : nullptr;
    }

    if (spac != 0) // 最后的进位处理
    {
        ListNode *newNode = new ListNode(spac);
        // 链表插入到哨兵节点后面
        newNode->next = dummy->next;
        dummy->next = newNode;
    }

    return dummy->next;
}

4、LCR 026. 重排链表

题目信息：

• https://leetcode.cn/problems/LGjMqU/description/

给定一个单链表 L 的头节点 head ，单链表 L 表示为：
 L0 → L1 → … → Ln-1 → Ln
请将其重新排列后变为：
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1：
输入: head = [1,2,3,4]
输出: [1,4,2,3]

示例 2：
输入: head = [1,2,3,4,5]
输出: [1,5,2,4,3]

提示：
链表的长度范围为 [1, 5 * 104]
1 <= node.val <= 1000

解题思路：

• 1、审题：输入一个链表，例如链表节点数据内容为（1,2,3,4,5,6），对链表重新排列，排列后的链表内容为(1,6,2,5,3,4)
• 2、解题：
• 先将链表分成两段，使用快慢指针实现，找到链表的中间节点
• 将后半部分的链表进行翻转，
• 最后将链表的前半部分数据段和翻转后的部分链表进行合并，没有返回说明是在原始链表中处理

代码实现：

void mergeList(ListNode *node1, ListNode *node2)
{
    ListNode *tempNode = new ListNode();

    while (node1 != nullptr || node2 != nullptr)
    {
        tempNode->next = node1;
        node1 = node1->next;
        tempNode = tempNode->next;

        if (node2 != nullptr)
        {
            tempNode->next = node2;
            node2 = node2->next;
            tempNode = tempNode->next;
        }
    }
}

void reorderList(ListNode *head)
{
    // 1、快慢指针找链表中间节点,使用哨兵节点
    ListNode *dummy = new ListNode();
    dummy->next = head;
    ListNode *slow = dummy;
    ListNode *fast = dummy->next;

    while (slow != nullptr && fast != nullptr)
    {
        slow = slow->next;
        fast = fast->next;
        if (fast != nullptr)
        {
            fast = fast->next;
        }
    }

    // 2、 找到中间节点，将链表截断
    ListNode *mid = slow->next;
    slow->next = nullptr;
    // 翻转链表
    ListNode *temp = reverseList(mid);

    // 3、将两个链表合并
    mergeList(head, temp);
}

5、LCR 027. 回文链表

题目信息：

• https://leetcode.cn/problems/aMhZSa/description/

给定一个链表的 头节点 head ，请判断其是否为回文链表。
如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

示例 1：
输入: head = [1,2,3,3,2,1]
输出: true

示例 2：
输入: head = [1,2]
输出: false

提示：
链表 L 的长度范围为 [1, 105]
0 <= node.val <= 9
进阶：能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

解题思路：

• 1、审题：输入一个链表，判断该链表是否是回文链表
• 2、解题：
• 暴力解法：遍历链表，将链表节点数据保存到数组中，然后判断数组中的数据是否是回文
• 链表翻转判断
• 回文链表与回文字符串一样的道理，要求链表从正向或者从反向遍历获取到的结点内容都一样
• 实现思路：使用快慢指针将链表截断成两个部分，将后面部分翻转，然后同时遍历两个链表节点，看是否相同

代码实现：

bool isPalindrome(ListNode *head)
{
    if (head == nullptr || head->next == nullptr)
    {
        return true;
    }
    // 使用快慢指针查找中间节点
    ListNode *fast = head->next;
    ListNode *slow = head;

    // 获取中间节点，并截断,需要找到中间节点的前一个结点指针
    while (fast->next != nullptr && fast->next->next != nullptr)
    {
        slow = slow->next;
        fast = fast->next->next;
    }

    ListNode *midNode = slow->next;
    slow->next = nullptr;
    
    // 翻转后半部分链表
    ListNode *reverse = reverseList(midNode);
    ListNode *node = head;

    // 遍历
    while (node != nullptr && reverse != nullptr)
    {
        if (node->val != reverse->val)
        {
            return false;
        }
        node = node->next;
        reverse = reverse->next;
    }

    return true;
}

6、总结：

• 链表翻转操作，需要使用三个节点变量来完成原始链表的遍历，和节点的指向
• 链表结点中的数字相加处理，都是在链表翻转基础上实现的。