题解 | #重排链表#

重排链表

https://www.nowcoder.com/practice/3d281dc0b3704347846a110bf561ef6b

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *reverseList(ListNode *head) {
        if (!head || !head->next) {
            return head;
        }
        ListNode *res = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return res;
    }

    void reorderList(ListNode *head) {
        if (!head || !head->next) {
            return;
        }
        ListNode *fast = head;
        ListNode *slow = head;
        ListNode *bef = nullptr;
        while (fast && fast->next) {
            fast = fast->next->next;
            bef = slow;
            slow = slow->next;
        }
        bef->next = nullptr;
        slow = reverseList(slow);
        ListNode *res = nullptr;
        ListNode **pt = &res;
        while (head) {
            *pt = head;
            head = head->next;
            pt = &((*pt)->next);
            *pt = slow;
            slow = slow->next;
            pt = &((*pt)->next);
        }
        if (slow) {
            *pt = slow;
            slow = slow->next;
            pt = &((*pt)->next);
        }
        head = res;
    }
};

思路:先分成两个链表,一个从前往后,一个从后往前(反转链表),然后再一个个节点合成即可。

链表结点个数可能为奇数个,所以最后反转链表可能多出来一个,特殊处理。

全部评论

相关推荐

05-12 17:00
门头沟学院 Java
king122:你的项目描述至少要分点呀,要实习的话,你的描述可以使用什么技术,实现了什么难点,达成了哪些数字指标,这个数字指标尽量是真实的,这样面试应该会多很多,就这样自己包装一下,包装不好可以找我,我有几个大厂最近做过的实习项目也可以包装一下
点赞 评论 收藏
分享
找个工作 学历是要卡的 要求是高的 技能不足是真的 实习经验是0的 简历无处可写是事实的 钱不好赚是真的 想躺平又不敢躺 也不甘心躺 怕自己的灵感和才华被掩埋甚至从未被自己发现 又质疑自己是否真正有才华
码农索隆:你现在啊,你心里都明白咋回事,但是你没办法改变现状,一想到未来,你又没有信心狠下心来在当下努力。 得走出这种状态,不能一直困在那里面,哪不行就去提升哪,你一动不动那指定改变不了未来,动起来,积少成多才能越来越好
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务