在这里插入图片描述
通过画图分析,可以从反转后链表与原链表中按顺序各自取一个结点来构建结果,不过要注意的这两个链表只会用到一半,结合 链表的中间结点 和 反转链表 进行解题。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    // 876. 链表的中间结点
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }

    // 206. 反转链表
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while (cur != nullptr) {
            ListNode* tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
    
    void reorderList(ListNode* head) {
        // 通过画图分析,可以从反转后链表与原链表中按顺序各自取一个结点来构建结果,不过要注意的这两个链表只会用到一半
        // 结合 链表的中间结点 和 反转链表 进行解题

        ListNode* mid = middleNode(head);
        ListNode* head2 = reverseList(mid); // 原链表中间位置后面进行反转

        // 问:循环条件 while head2.next 为什么不能写成 while head2?
        // 答:如果链表长度为偶数,例如链表由 [1,2,3,4,5,6] 组成,那么找中间节点 4 并反转后,我们得到的两个链表分别为
        // head=[1,2,3,4] 和 head2=[6,5,4]。注意它俩都包含节点 4,如果写成 while head2,会导致结果中有两个 4
        // 模拟一下head:
        
        // 第一轮 1->6->2 ->3->4
        // 第二轮:1->6->2->5->3 ->4  得出结果,此时head2->next = nullptr,如果还继续循环,那么会得到1->6->2->5->3->4->4
        while (head2->next) {
            ListNode* tmp = head->next;
            ListNode* tmp2 = head2->next;
            head->next = head2;
            head2->next = tmp;
            head = tmp;
            head2 = tmp2;
        }

    }
};

这道题相当于考察了三道题,包括 求链表中间节点(双指针)和 反转链表(pre)。

关于循环条件 while head2.next 为什么不能写成 while head2?可以看下面这个图:
在这里插入图片描述

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部